The polynomial-time hierarchy and sparse oracles

DOI10.1145/5925.5937zbMATH Open0625.68033OpenAlexW2024309621MaRDI QIDQ3028343FDOQ3028343

Authors: José L. Balcázar, Ronald V. Book, Uwe Schöning 

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

Recommendations

• The polynomial-time hierarchy and oracle set \(A \in \text{PH/poly}\)
• scientific article; zbMATH DE number 4080915
• scientific article; zbMATH DE number 3883613
• \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
• Relativized Polynomial Time Hierarchies Having Exactly K Levels

zbMATH Keywords

complexity classessparserelativizationspolynomial-time hierarchysparse setsparse oracle set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (38)

• On complexity classes and algorithmically random languages
• \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
• A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly
• Strong and robustly strong polynomial-time reducibilities to sparse sets
• Separating complexity classes with tally oracles
• The effect of combination functions on the complexity of relational Bayesian networks
• A very hard log-space counting class
• Hard promise problems and nonuniform complexity
• Tally NP sets and easy census functions.
• A note on sparse sets and the polynomial-time hierarchy
• The polynomial-time hierarchy and oracle set \(A \in \text{PH/poly}\)
• Some connections between bounded query classes and non-uniform complexity.
• Self-reducible sets of small density
• Turing machines with few accepting computations and low sets for PP
• The complexity of power-index comparison
• Logarithmic advice classes
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• Hyper-polynomial hierarchies and the polynomial jump
• New collapse consequences of NP having small circuits
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
• Simple characterizations of \(P(\# P)\) and complete problems
• Title not available (Why is that?)
• Separating the low and high hierarchies by oracles
• Approximate inference in Bayesian networks: parameterized complexity results
• Complexity classes and sparse oracles
• Restricted relativizations of probabilistic polynomial time
• Manipulating the quota in weighted voting games
• Nonuniform lowness and strong nonuniform lowness
• Title not available (Why is that?)
• Competing provers yield improved Karp-Lipton collapse results
• On hiding information from an oracle
• Self-reducibility
• Relativized Polynomial Time Hierarchies Having Exactly K Levels
• Proper hierarchies in polylogarithmic time and absence of complete problems
• On bounded query machines
• An observation on probability versus randomness with applications to complexity classes
• Relativized isomorphisms of NP-complete sets
• The polynomial hierarchy for some structures over the binary words

This page was built for publication: The polynomial-time hierarchy and sparse oracles

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