The Boolean Hierarchy II: Applications

DOI10.1137/0218007zbMath0676.68012OpenAlexW2010937503MaRDI QIDQ3832043

Vivian Sewelson, Hemaspaandra, Lane A., Gerd Wechsung, Thomas Gundermann, Jin-Yi Cai, Klaus W. Wagner, Juris Hartmanis

Publication date: 1989

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0218007

zbMATH Keywords

sparse setscomplexity classesnonuniform complexity classescounting classesboolean hierarchy

Mathematics Subject Classification ID

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

Related Items (32)

The random oracle hypothesis is false ⋮ A complexity theory for feasible closure properties ⋮ A downward translation 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 ⋮ Simultaneous strong separations of probabilistic and unambiguous complexity classes ⋮ The complexity of computing minimal unidirectional covering sets ⋮ Universally serializable computation ⋮ On the power of parity polynomial time ⋮ Intersection suffices for Boolean hierarchy equivalence ⋮ Unnamed Item ⋮ New developments in structural complexity theory ⋮ Lower bounds for constant-depth circuits in the presence of help bits ⋮ On the complexity of test case generation for NP-hard problems ⋮ On truth-table reducibility to SAT ⋮ Strong self-reducibility precludes strong immunity ⋮ Separating complexity classes with tally oracles ⋮ On the power of parity polynomial time ⋮ The 1-versus-2 queries problem revisited ⋮ Lower bounds and the hardness of counting properties ⋮ Cognitive hierarchy and voting manipulation in \(k\)-approval voting ⋮ The robustness of LWPP and WPP, with an application to graph reconstruction ⋮ 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 ⋮ 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 ⋮ A Downward Collapse within the Polynomial Hierarchy ⋮ Query Order ⋮ All superlinear inverse schemes are coNP-hard ⋮ Commutative queries ⋮ Bounded queries, approximations, and the Boolean hierarchy

This page was built for publication: The Boolean Hierarchy II: Applications