The Boolean Hierarchy II: Applications
From MaRDI portal
Publication:3832043
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
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
