The strong exponential hierarchy collapses
From MaRDI portal
Publication:584250
DOI10.1016/0022-0000(89)90025-1zbMath0693.03022OpenAlexW1973023438MaRDI QIDQ584250
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
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Hierarchies of computability and definability (03D55)
Related Items (43)
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
This page was built for publication: The strong exponential hierarchy collapses
