The strong exponential hierarchy collapses

DOI10.1016/0022-0000(89)90025-1zbMath0693.03022MaRDI QIDQ584250

Hemaspaandra, Lane A.

Publication date: 1989

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(89)90025-1

zbMATH Keywords

nondeterminism; complexity classes; census counting techniques; strong exponential hierarchy

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03D15: Complexity of computation (including implicit computational complexity)

03D55: Hierarchies of computability and definability

Related Items

Generalized theorems on relationships among reducibility notions to certain complexity classes, COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA, On computing Boolean connectives of characteristic functions, Upper bounds for the complexity of sparse and tally descriptions, Weak cardinality theorems, The strong exponential hierarchy collapses, Probabilistic polynomial time is closed under parity reductions, Kolmogorov characterizations of complexity classes, The complexity of Kemeny elections, \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP], On truth-table reducibility to SAT, Bounded queries to SAT and the Boolean hierarchy, Polynomial-time compression, Succinctness as a source of complexity in logical formalisms, Census techniques collapse space classes, Separating classes in the exponential-time hierarchy from classes in PH, On parallel hierarchies and \(R_k^i\), Tally NP sets and easy census functions., Bounded queries, approximations, and the Boolean hierarchy, Optimal series-parallel trade-offs for reducing a function to its own graph, Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP, On the power of deterministic reductions to C=P

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The strong exponential hierarchy collapses
• Qualitative relativizations of complexity classes
• Structure in complexity theory. Proceedings of the Conference held at the University of California, Berkeley, California, June 2-5, 1986
• \(\Sigma_ 2SPACE(n)\) is closed under complement
• Complexity classes without machines: on complete languages for UP
• On sparse oracles separating feasible complexity classes
• Bounded query machines: on NP and PSPACE
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Bounded queries to SAT and the Boolean hierarchy
• A comparison of polynomial time reducibilities
• The polynomial-time hierarchy
• Computation times of NP sets of different densities
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• Positive Relativizations of Complexity Classes
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Quantitative Relativizations of Complexity Classes
• The difference and truth-table hierarchies for NP
• Erratum: On Restricting the Size of Oracles Compared with Restricting Access to Oracles
• Nondeterministic Space is Closed under Complementation
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• Alternation
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On the Computational Complexity of Algorithms