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
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.
