The Boolean Hierarchy I: Structural Properties
From MaRDI portal
Publication:3832042
DOI10.1137/0217078zbMath0676.68011OpenAlexW2090039116MaRDI QIDQ3832042
Vivian Sewelson, Thomas Gundermann, Jin-Yi Cai, Hemaspaandra, Lane A., Gerd Wechsung, Juris Hartmanis, Klaus W. Wagner
Publication date: 1988
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0217078
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (60)
The random oracle hypothesis is false ⋮ A complexity theory for feasible closure properties ⋮ Reasoning with power defaults ⋮ A relationship between difference hierarchies and relativized polynomial hierarchies ⋮ Guarantees for the success frequency of an algorithm for finding Dodgson-election winners ⋮ A downward translation in the polynomial hierarchy ⋮ A Survey on Difference Hierarchies of Regular Languages ⋮ Efficient algorithms for membership in Boolean hierarchies of regular languages ⋮ The complexity class θp2: Recent results and applications in AI and modal logic ⋮ Query order in the polynomial hierarchy ⋮ Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games ⋮ Polynomial terse sets ⋮ Simultaneous strong separations of probabilistic and unambiguous complexity classes ⋮ Cluster computing and the power of edge recognition ⋮ Complexity classes without machines: on complete languages for UP ⋮ Bounded query classes and the difference hierarchy ⋮ On computing Boolean connectives of characteristic functions ⋮ The complexity of computing minimal unidirectional covering sets ⋮ Universally serializable computation ⋮ Mind change speed-up for learning languages from positive data ⋮ Characterizing and extending answer set semantics using possibility theory ⋮ On the power of deterministic reductions to C=P ⋮ Intersection suffices for Boolean hierarchy equivalence ⋮ On the complexity of automatic complexity ⋮ From \texttt{SAT} to \texttt{SAT}-\texttt{UNSAT} using P systems with dissolution rules ⋮ Observations on complete sets between linear time and polynomial time ⋮ \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP] ⋮ From NP-completeness to DP-completeness: a membrane computing perspective ⋮ New developments in structural complexity theory ⋮ Kolmogorov complexity and degrees of tally sets ⋮ On the complexity of test case generation for NP-hard problems ⋮ The Boolean hierarchy of NP-partitions ⋮ On truth-table reducibility to SAT ⋮ Strong self-reducibility precludes strong immunity ⋮ Acceptance in incomplete argumentation frameworks ⋮ The complexity of unions of disjoint sets ⋮ A uniform approach to define complexity classes ⋮ On the power of parity polynomial time ⋮ Quantum and classical complexity classes: Separations, collapses, and closure properties ⋮ The 1-versus-2 queries problem revisited ⋮ On boolean lowness and boolean highness ⋮ Cognitive hierarchy and voting manipulation in \(k\)-approval voting ⋮ The strong exponential hierarchy collapses ⋮ Function operators spanning the arithmetical and the polynomial hierarchy ⋮ Reductions to sets of low information content ⋮ Exact complexity of exact-four-colorability ⋮ Complexity classes between $\Theta _k^P$ and $\Delta _k^P$ ⋮ Hybrid Elections Broaden Complexity-Theoretic Resistance to Control ⋮ On Existentially First-Order Definable Languages and Their Relation to NP ⋮ A second step towards complexity-theoretic analogs of Rice's Theorem ⋮ The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions ⋮ Query Order ⋮ The closure of monadic NP ⋮ All superlinear inverse schemes are coNP-hard ⋮ Resource bounded immunity and simplicity ⋮ On qualitative route descriptions. Representation, agent models, and computational complexity ⋮ Commutative queries ⋮ Bounded queries, approximations, and the Boolean hierarchy ⋮ A note on parallel queries and the symmetric-difference hierarchy. ⋮ Reducing the number of solutions of NP functions
This page was built for publication: The Boolean Hierarchy I: Structural Properties
