• DocumentCode
    2188329
  • Title

    A natural encoding scheme proved probabilistic polynomial complete

  • Author

    Vazirani, Umesh V. ; Vazirani, Vijay V. ; Vazirani, Umesh V. ; Vazirani, Umesh V. ; Vazirani, Vijay V. ; Vazirani, Vijay V. ; Vazirani, Vijay V. ; Vazirani, Vijay V.

  • fYear
    1982
  • fDate
    3-5 Nov. 1982
  • Firstpage
    40
  • Lastpage
    44
  • Abstract
    We prove a natural encoding scheme intractable (by showing it UR-complete, a technique which may be used when a problem does not yield to a proof of NP-completeness). This is the first non number-theoretic problem that is UR-complete but not known to be NP-complete. We also redefine UR-completeness (henceforth refered to as PR-completeness) in probabilistic terms thus making the notion conceptually simpler. Our result suggests that PR-completeness may be a more widely applicable technique than was previously believed.
  • Keywords
    Encoding; NP-complete problem; Polynomials; Scholarships; Turing machines;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1982. SFCS '08. 23rd Annual Symposium on
  • Conference_Location
    Chicago, IL, USA
  • ISSN
    0272-5428
  • Type

    conf

  • DOI
    10.1109/SFCS.1982.54
  • Filename
    4568372
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2188329