DSPACE(n) ? = NSPACE(n): A degree theoretic characterization

DOI10.1006/JCSS.1997.1483zbMATH Open0882.68061OpenAlexW2058290996MaRDI QIDQ1362330FDOQ1362330

Authors: 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

Recommendations

• If deterministic and nondeterministic space complexities are equal for \(\log \log n\) then they are also equal for \(\log n\)
• If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n
• scientific article
• Collapsing degrees via strong computation

zbMATH Keywords

structure of complete degrees

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (1)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1362330)