New developments in structural complexity theory

DOI10.1016/0304-3975(90)90191-JzbMath0699.68065OpenAlexW2120111623MaRDI QIDQ913509

Juris Hartmanis

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

zbMATH Keywords

surveystructural complexity theory

Mathematics Subject Classification ID

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