New developments in structural complexity theory
From MaRDI portal
Publication:913509
DOI10.1016/0304-3975(90)90191-JzbMath0699.68065OpenAlexW2120111623MaRDI QIDQ913509
Publication date: 1990
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(90)90191-j
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (6)
Development of metrics and a complexity scale for the topology of assembly supply chains ⋮ An NL hierarchy ⋮ A survey of space complexity ⋮ Removing redundancy from a clause ⋮ On the complexity of propositional knowledge base revision, updates, and counterfactuals ⋮ Bridging across the \(\log(n)\) space frontier
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Some consequences of non-uniform conditions on uniform classes
- Space-bounded hierarchies and probabilistic computations
- Relativized circuit complexity
- Structure in complexity theory. Proceedings of the Conference held at the University of California, Berkeley, California, June 2-5, 1986
- Reductions among polynomial isomorphism types
- Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\)
- A note on sparse oracles for NP
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- The polynomial-time hierarchy
- Complete sets and the polynomial-time hierarchy
- Computation times of NP sets of different densities
- Relationships between nondeterministic and deterministic tape complexities
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- Nondeterministic Space is Closed under Complementation
- The Boolean Hierarchy I: Structural Properties
- The Boolean Hierarchy II: Applications
- Limitations on Separating Nondeterministic Complexity Classes
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Relativization of questions about log space computability
- On Isomorphisms and Density of $NP$ and Other Complete Sets
This page was built for publication: New developments in structural complexity theory
