A natural encoding scheme proved probabilistic polynomial complete
Umesh V. Vazirani, Vijay V. Vazirani · 1982
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.