The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses

DOI10.1137/0217080zbMath0664.03031OpenAlexW2053094807MaRDI QIDQ3815290

Jim Kadin

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

zbMATH Keywords

collapseBoolean hierarchypolynomial time hierarchycomplexity hierarchiesparallel query hierarchyquery hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

The random oracle hypothesis is false ⋮ Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete ⋮ A relationship between difference hierarchies and relativized polynomial hierarchies ⋮ Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP ⋮ Guarantees for the success frequency of an algorithm for finding Dodgson-election winners ⋮ A downward translation in the polynomial hierarchy ⋮ Query order in the polynomial hierarchy ⋮ Structural complexity theory: Recent surprises ⋮ Complexity results in graph reconstruction ⋮ The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\) ⋮ On computing Boolean connectives of characteristic functions ⋮ A refinement of the low and high hierarchies ⋮ Structural analysis of the complexity of inverse functions ⋮ On the power of deterministic reductions to C=P ⋮ Intersection suffices for Boolean hierarchy equivalence ⋮ Observations on complete sets between linear time and polynomial time ⋮ \(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 ⋮ Two queries ⋮ The Boolean hierarchy of NP-partitions ⋮ A Tight Karp-Lipton Collapse Result in Bounded Arithmetic ⋮ The 1-Versus-2 Queries Problem Revisited ⋮ Why not negation by fixpoint? ⋮ THE THOMPSON–HIGMAN MONOIDS M_k,i: THE ${\mathcal J}$-ORDER, THE ${\mathcal D}$-RELATION, AND THEIR COMPLEXITY ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ Removing redundancy from a clause ⋮ Proving SAT does not have small circuits with an application to the two queries problem ⋮ The 1-versus-2 queries problem revisited ⋮ On boolean lowness and boolean highness ⋮ Nondeterministic and randomized Boolean hierarchies in communication complexity ⋮ THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS ⋮ Relations between communication complexity classes ⋮ Bounded queries to arbitrary sets ⋮ Enumerative counting is hard ⋮ A Downward Collapse within the Polynomial Hierarchy ⋮ Query Order ⋮ Multifunction algebras and the provability of \(PH\downarrow\) ⋮ Commutative queries ⋮ Bounded queries, approximations, and the Boolean hierarchy ⋮ On adaptive versus nonadaptive bounded query machines ⋮ On the computational complexity of qualitative coalitional games