The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
From MaRDI portal
Recommendations
Cited in
(54)- [[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]
- Why not negation by fixpoint?
- Bounded queries to SAT and the Boolean hierarchy
- Elimination of parameters in the polynomial hierarchy
- On bounded-probability operators and C\(_ =\)P
- The random oracle hypothesis is false
- Multifunction algebras and the provability of PH
- Enumerative counting is hard
- Commutative queries
- Bounded queries, approximations, and the Boolean hierarchy
- Two queries
- Nondeterministic and randomized Boolean hierarchies in communication complexity
- 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
- Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
- The Thompson-Higman monoids \(M_{k,i}\): the \(\mathcal J\)-order, the \(\mathcal D\)-relation, and their complexity.
- Separating and collapsing results on the relativized probabilistic polynomial-time hierarchy
- A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
- scientific article; zbMATH DE number 3950504 (Why is no real title available?)
- scientific article; zbMATH DE number 4080916 (Why is no real title available?)
- scientific article; zbMATH DE number 17529 (Why is no real title available?)
- On the Structure of Bounded Queries to Arbitrary NP Sets
- 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
- Bounded queries to arbitrary sets
- On computing Boolean connectives of characteristic functions
- A refinement of the low and high hierarchies
- The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
- A downward translation in the polynomial hierarchy
- Query order in the polynomial hierarchy
- Structural complexity theory: Recent surprises
- A relationship between difference hierarchies and relativized polynomial hierarchies
- Extending Downward Collapse from 1-versus-2 Queries tom-versus-m+ 1 Queries
- The 1-Versus-2 Queries Problem Revisited
- THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS
- The strong exponential hierarchy collapses
- On boolean lowness and boolean highness
- Intersection suffices for Boolean hierarchy equivalence
- Observations on complete sets between linear time and polynomial time
- Nondeterministic and randomized Boolean hierarchies in communication complexity
- 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
This page was built for publication: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3815290)
