Bounded queries to SAT and the Boolean hierarchy

DOI10.1016/0304-3975(91)90160-4zbMath0739.68035OpenAlexW2063158069MaRDI QIDQ1178690

Richard Beigel

Publication date: 26 June 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90160-4

zbMATH Keywords

Boolean hierarchybounded queriesdifference hierarchiesp-tersenessrounds of queriesseparation of the hierarchies of functions

Mathematics Subject Classification ID

Related Items (37)

Amplification with one \textsf{NP} oracle query ⋮ A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly ⋮ A relationship between difference hierarchies and relativized polynomial hierarchies ⋮ Locating \(P\)/poly optimally in the extended low hierarchy ⋮ The power of frequency computation ⋮ The complexity class θp2: Recent results and applications in AI and modal logic ⋮ Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria ⋮ Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games ⋮ The landscape of communication complexity classes ⋮ Bounded query classes and the difference hierarchy ⋮ Unnamed Item ⋮ On computing Boolean connectives of characteristic functions ⋮ Mind change speed-up for learning languages from positive data ⋮ Characterizations of some complexity classes between Θ2p and Δ2p ⋮ Promise problems and access to unambiguous computation ⋮ Bi-immunity results for cheatable sets ⋮ Some connections between bounded query classes and non-uniform complexity. ⋮ A Tight Karp-Lipton Collapse Result in Bounded Arithmetic ⋮ On quasilinear-time complexity theory ⋮ Unnamed Item ⋮ The strong exponential hierarchy collapses ⋮ Consequences of the provability of NP ⊆ P/poly ⋮ The communication complexity of enumeration, elimination, and selection ⋮ Nondeterministic and randomized Boolean hierarchies in communication complexity ⋮ Unnamed Item ⋮ Exact complexity of exact-four-colorability ⋮ Probabilistic polynomial time is closed under parity reductions ⋮ Bounded queries to arbitrary sets ⋮ Complexity classes between $\Theta _k^P$ and $\Delta _k^P$ ⋮ On the complexity of finding the chromatic number of a recursive graph. I: The bounded case ⋮ Query Order ⋮ Commutative queries ⋮ Bounded queries, approximations, and the Boolean hierarchy ⋮ Optimal series-parallel trade-offs for reducing a function to its own graph ⋮ A note on parallel queries and the symmetric-difference hierarchy. ⋮ On adaptive versus nonadaptive bounded query machines ⋮ A note on enumerative counting

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The strong exponential hierarchy collapses
• Bi-immunity results for cheatable sets
• The complexity of facets (and some facets of complexity)
• Polynomial terse sets
• The complexity of optimization problems
• Bounded query classes and the difference hierarchy
• Terse, superterse, and verbose sets
• Using self-reducibilities to characterize polynomial time
• On the Inversion Complexity of a System of Functions
• Bounded Query Classes
• The difference and truth-table hierarchies for NP
• On Sets Truth-Table Reducible to Sparse Sets
• A cardinality version of Beigel's nonspeedup theorem
• Trial and error predicates and the solution to a problem of Mostowski

This page was built for publication: Bounded queries to SAT and the Boolean hierarchy