Polynomial-time reducibilities and ``almost all oracle sets

DOI10.1016/0304-3975(91)90314-RzbMath0719.03020OpenAlexW1968283763MaRDI QIDQ2639849

Ronald V. Book, Shouwen Tang

Publication date: 1991

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90314-r

zbMATH Keywords

polynomial-timetally setreducibilitiesoracle sets

Mathematics Subject Classification ID

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

Related Items

Genericity and measure for exponential time, Bounded truth table does not reduce the one-query tautologies to a random oracle, An excursion to the Kolmogorov random strings, An observation on probability versus randomness with applications to complexity classes, Characterizing polynomial complexity classes by reducibilities, On independent random oracles, Does truth-table of linear norm reduce the one-query tautologies to a random oracle?, On the robustness of ALMOST-$\mathcal {R}$, Genericity and measure for exponential time

Cites Work

• Unnamed Item
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• A comparison of polynomial time reducibilities
• On Sets Truth-Table Reducible to Sparse Sets
• On Tally Relativizations of $BP$-Complexity Classes
• Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1