The strong exponential hierarchy collapses

DOI10.1016/0022-0000(89)90025-1zbMath0693.03022OpenAlexW1973023438MaRDI 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

nondeterminismcomplexity classescensus counting techniquesstrong exponential hierarchy

Mathematics Subject Classification ID

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

Related Items

Inconsistency-tolerant query answering for existential rules, Census techniques collapse space classes, COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA, Guarantees for the success frequency of an algorithm for finding Dodgson-election winners, Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games, Equivalence between model-checking flat counter systems and Presburger arithmetic, Combining answer set programming with description logics for the semantic web, Separating classes in the exponential-time hierarchy from classes in PH, Generalized theorems on relationships among reducibility notions to certain complexity classes, Controlling weighted voting games by deleting or adding players with or without changing the quota, Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP, On parallel hierarchies and \(R_k^i\), On computing Boolean connectives of characteristic functions, On the power of unambiguity in log-space, Promise problems and access to unambiguous computation, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, On the power of deterministic reductions to C=P, Mixed Iterated Revisions: Rationale, Algorithms, and Complexity, Stability, vertex stability, and unfrozenness for special graph classes, Upper bounds for the complexity of sparse and tally descriptions, \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP], On truth-table reducibility to SAT, The Complexity Landscape of Outcome Determination in Judgment Aggregation, FLP answer set semantics without circular justifications for general logic programs, Bounded queries to SAT and the Boolean hierarchy, On the cutting edge of relativization: The resource bounded injury method, Complexity of stability, Weak cardinality theorems, Complexity of Stability., Polynomial-time compression, The strong exponential hierarchy collapses, Structural properties of oracle classes, Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP, Knowledge-based programs as succinct policies for partially observable domains, Probabilistic polynomial time is closed under parity reductions, Rational closure for all description logics, Succinctness as a source of complexity in logical formalisms, Preference-based inconsistency-tolerant query answering under existential rules, 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, Kolmogorov characterizations of complexity classes, The complexity of Kemeny elections

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