The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
From MaRDI portal
Publication:3815290
DOI10.1137/0217080zbMath0664.03031MaRDI QIDQ3815290
Publication date: 1988
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/6683
collapse; Boolean hierarchy; polynomial time hierarchy; complexity hierarchies; parallel query hierarchy; query hierarchy
68Q25: Analysis of algorithms and problem complexity
03D15: Complexity of computation (including implicit computational complexity)
Related Items
Bounded queries to arbitrary sets, On computing Boolean connectives of characteristic functions, A refinement of the low and high hierarchies, A relationship between difference hierarchies and relativized polynomial hierarchies, The 1-Versus-2 Queries Problem Revisited, THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS, On boolean lowness and boolean highness, Removing redundancy from a clause, Relations between communication complexity classes, On adaptive versus nonadaptive bounded query machines, On the computational complexity of qualitative coalitional games, Guarantees for the success frequency of an algorithm for finding Dodgson-election winners, Complexity results in graph reconstruction, \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP], New developments in structural complexity theory, Lower bounds for constant-depth circuits in the presence of help bits, The Boolean hierarchy of NP-partitions, Fine hierarchies and m-reducibilities in theoretical computer science, The 1-versus-2 queries problem revisited, The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\), Why not negation by fixpoint?, The random oracle hypothesis is false, Multifunction algebras and the provability of \(PH\downarrow\), Enumerative counting is hard, Commutative queries, Bounded queries, approximations, and the Boolean hierarchy, Two queries, Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete, Proving SAT does not have small circuits with an application to the two queries problem, A Tight Karp-Lipton Collapse Result in Bounded Arithmetic, Structural analysis of the complexity of inverse functions, On the power of deterministic reductions to C=P, A Downward Collapse within the Polynomial Hierarchy, Query Order
