Characterizing polynomial complexity classes by reducibilities

DOI10.1007/BF02090773zbMath0707.68035OpenAlexW2019893603MaRDI QIDQ3489449

Ronald V. Book, Shouwen Tang

Publication date: 1990

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02090773

zbMATH Keywords

reducibilitycharacterizationspolynomial-time hierarchystructural complexityclasses \(\Sigma ^ P_ k\)

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On random oracle separations, Circuit size relative to pseudorandom oracles

Cites Work

• Unnamed Item
• Unnamed Item
• Strong nondeterministic polynomial-time reducibilities
• Qualitative relativizations of complexity classes
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Positive relativizations of the \(P=?\) NP problem
• A comparison of polynomial time reducibilities
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• Hardness vs randomness
• Polynomial-time reducibilities and ``almost all oracle sets
• On Tally Relativizations of $BP$-Complexity Classes
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Computational Complexity of Probabilistic Turing Machines