The Boolean Hierarchy II: Applications

DOI10.1137/0218007MaRDI QIDQ3832043zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Thomas Gundermann, Lane A. Hemaspaandra, Vivian Sewelson, Gerd Wechsung, J. Hartmanis, K. W. Wagner

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

boolean hierarchycomplexity classescounting classesnonuniform complexity classessparse sets

Mathematics Subject Classification ID

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

Recommendations

• The Boolean Hierarchy I: Structural Properties
• scientific article; zbMATH DE number 3988706
• scientific article; zbMATH DE number 1500515
• scientific article; zbMATH DE number 1222828
• scientific article; zbMATH DE number 4045650

Cited in

(38)

• Exact complexity of exact-four-colorability
• The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions
• On truth-table reducibility to SAT
• Separating complexity classes with tally oracles
• The random oracle hypothesis is false
• Universally serializable computation
• A second step towards complexity-theoretic analogs of Rice's Theorem
• Commutative queries
• Bounded queries, approximations, and the Boolean hierarchy
• Cognitive hierarchy and voting manipulation in \(k\)-approval voting
• The robustness of LWPP and WPP, with an application to graph reconstruction
• A complexity theory for feasible closure properties
• All superlinear inverse schemes are coNP-hard
• Function operators spanning the arithmetical and the polynomial hierarchy
• Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games
• scientific article; zbMATH DE number 3988706 (Why is no real title available?)
• scientific article; zbMATH DE number 4045650 (Why is no real title available?)
• The Boolean Hierarchy I: Structural Properties
• Simultaneous strong separations of probabilistic and unambiguous complexity classes
• A Downward Collapse within the Polynomial Hierarchy
• Query Order
• scientific article; zbMATH DE number 1875976 (Why is no real title available?)
• Strong self-reducibility precludes strong immunity
• The robustness of LWPP and WPP, with an application to graph reconstruction
• A downward translation in the polynomial hierarchy
• On the power of parity polynomial time
• Reductions to sets of low information content (extended abstract)
• On the power of parity polynomial time
• The strong exponential hierarchy collapses
• Intersection suffices for Boolean hierarchy equivalence
• Broadcast graph is NP-complete
• Gaps, ambiguity, and establishing complexity-class containments via iterative constant-setting
• Lower bounds and the hardness of counting properties
• Which graph motif parameters count?
• 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
• The 1-versus-2 queries problem revisited

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3832043)