DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization

DOI10.1006/jcss.1997.1483zbMath0882.68061OpenAlexW2058290996MaRDI QIDQ1362330

Manindra Agrawal

Publication date: 3 August 1997

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

Full work available at URL: https://doi.org/10.1006/jcss.1997.1483

zbMATH Keywords

structure of complete degrees

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Reductions in circuit complexity: An isomorphism theorem and a gap theorem

Cites Work

• Unnamed Item
• Unnamed Item
• On one-one polynomial time equivalence relations
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• On one-way functions and polynomial-time isomorphisms
• The method of forced enumeration for nondeterministic automata
• Isomorphisms and 1-L reductions
• On log-tape isomorphisms of complete sets
• On the isomorphism conjecture for weak reducibilities
• Nondeterministic Space is Closed under Complementation
• Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• The isomorphism conjecture fails relative to a random oracle
• Complete problems and strong polynomial reducibilities
• The degree structure of 1-L reductions

This page was built for publication: DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization