A natural encoding scheme proved probabilistic polynomial complete
From MaRDI portal
Publication:593778
DOI10.1016/0304-3975(83)90004-XzbMath0525.68025MaRDI QIDQ593778
Umesh V. Vazirani, Vijay V. Vazirani
Publication date: 1983
Published in: Theoretical Computer Science (Search for Journal in Brave)
Kolmogorov complexity; probabilistic Turing machines; encoding schemes; PR-completeness; probabilistic polynomial complete; unfaithful random complete; UR-completeness
68Q25: Analysis of algorithms and problem complexity
Related Items
On the power of generalized Mod-classes, On random reductions from sparse sets to tally sets, NP is as easy as detecting unique solutions, On polynomial-time Turing and many-one completeness in PSPACE
Cites Work