A natural encoding scheme proved probabilistic polynomial complete
From MaRDI portal
Publication:593778
DOI10.1016/0304-3975(83)90004-XzbMath0525.68025OpenAlexW2073340866MaRDI QIDQ593778
Vijay V. Vazirani, Umesh V. Vazirani
Publication date: 1983
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(83)90004-x
Kolmogorov complexityprobabilistic Turing machinesencoding schemesPR-completenessprobabilistic polynomial completeunfaithful random completeUR-completeness
Related Items
NP is as easy as detecting unique solutions, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, On the power of generalized Mod-classes, On polynomial-time Turing and many-one completeness in PSPACE, On random reductions from sparse sets to tally sets, The Complexity of Fixed-Height Patterned Tile Self-assembly
Cites Work