DSPACE(n) ? = NSPACE(n): A degree theoretic characterization
From MaRDI portal
Publication:1362330
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; zbMATH DE number 176750
- Collapsing degrees via strong computation
Cites work
- scientific article; zbMATH DE number 176750 (Why is no real title available?)
- scientific article; zbMATH DE number 1256638 (Why is no real title available?)
- Complete problems and strong polynomial reducibilities
- Isomorphisms and 1-L reductions
- Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
- Nondeterministic Space is Closed under Complementation
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- On log-tape isomorphisms of complete sets
- On one-one polynomial time equivalence relations
- On one-way functions and polynomial-time isomorphisms
- On the isomorphism conjecture for weak reducibilities
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- The degree structure of 1-L reductions
- The isomorphism conjecture fails relative to a random oracle
- The method of forced enumeration for nondeterministic automata
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)
