A natural encoding scheme proved probabilistic polynomial complete

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

zbMATH Keywords

Kolmogorov complexityprobabilistic Turing machinesencoding schemesPR-completenessprobabilistic polynomial completeunfaithful random completeUR-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (6)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the Structure of Polynomial Time Reducibility
• On the complexity of minimum inference of regular sets

This page was built for publication: A natural encoding scheme proved probabilistic polynomial complete