The polynomial-time hierarchy and sparse oracles
From MaRDI portal
Publication:3028343
DOI10.1145/5925.5937zbMath0625.68033OpenAlexW2024309621MaRDI QIDQ3028343
Ronald V. Book, José L. Balcázar, Uwe Schoening
Publication date: 1986
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/5925.5937
Related Items (27)
Simple characterizations of \(P(\# P)\) and complete problems ⋮ A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly ⋮ On bounded query machines ⋮ Nonuniform lowness and strong nonuniform lowness ⋮ Separating the low and high hierarchies by oracles ⋮ Self-reducibility ⋮ An observation on probability versus randomness with applications to complexity classes ⋮ Self-reducible sets of small density ⋮ The effect of combination functions on the complexity of relational Bayesian networks ⋮ On complexity classes and algorithmically random languages ⋮ Manipulating the quota in weighted voting games ⋮ Some connections between bounded query classes and non-uniform complexity. ⋮ Approximate inference in Bayesian networks: parameterized complexity results ⋮ Strong and robustly strong polynomial-time reducibilities to sparse sets ⋮ Separating complexity classes with tally oracles ⋮ Restricted relativizations of probabilistic polynomial time ⋮ Turing machines with few accepting computations and low sets for PP ⋮ New collapse consequences of NP having small circuits ⋮ Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P ⋮ Logarithmic advice classes ⋮ Relativized isomorphisms of NP-complete sets ⋮ A very hard log-space counting class ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ The complexity of power-index comparison ⋮ Hard promise problems and nonuniform complexity ⋮ On hiding information from an oracle ⋮ Tally NP sets and easy census functions.
This page was built for publication: The polynomial-time hierarchy and sparse oracles
