Characterizing polynomial complexity classes by reducibilities
DOI10.1007/BF02090773zbMATH Open0707.68035OpenAlexW2019893603MaRDI QIDQ3489449FDOQ3489449
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
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
characterizationsreducibilitystructural complexitypolynomial-time hierarchyclasses \(\Sigma ^ P_ k\)
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Title not available (Why is that?)
- Qualitative relativizations of complexity classes
- Hardness vs randomness
- Title not available (Why is that?)
- The polynomial-time hierarchy
- Computational Complexity of Probabilistic Turing Machines
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- A comparison of polynomial time reducibilities
- Complete sets and the polynomial-time hierarchy
- Strong nondeterministic polynomial-time reducibilities
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Positive relativizations of the \(P=?\) NP problem
- Polynomial-time reducibilities and ``almost all oracle sets
- On Tally Relativizations of $BP$-Complexity Classes
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
- Title not available (Why is that?)
- 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)
