Characterizing polynomial complexity classes by reducibilities

DOI10.1007/BF02090773MaRDI QIDQ3489449zbMATH OpenOpenAlexFDO

Authors 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

characterizationsreducibilitystructural complexitypolynomial-time hierarchyclasses \(\Sigma ^ P_ k\)

Mathematics Subject Classification ID

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

Recommendations

• Using self-reducibilities to characterize polynomial time
• scientific article; zbMATH DE number 4010508
• Characterizations of reduction classes modulo oracle conditions
• Generalized theorems on relationships among reducibility notions to certain complexity classes
• On Sets Truth-Table Reducible to Sparse Sets

Cites work

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

Cited in

(8)

• Nondiamond theorems for polynomial time reducibility
• Generalized theorems on relationships among reducibility notions to certain complexity classes
• Characterizing parallel hierarchies by reducibilities
• Circuit size relative to pseudorandom oracles
• scientific article; zbMATH DE number 3963808 (Why is no real title available?)
• On random oracle separations
• Characterizations of reduction classes modulo oracle conditions
• Computationally classifying polynomials with small Euclidean norm having reducible non-reciprocal parts

This page was built for publication: Characterizing polynomial complexity classes by reducibilities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3489449)