On log-tape isomorphisms of complete sets
From MaRDI portal
Publication:1249940
DOI10.1016/0304-3975(78)90018-XzbMATH Open0387.68035OpenAlexW2043113327MaRDI QIDQ1249940FDOQ1249940
Authors: J. Hartmanis 
Publication date: 1978
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(78)90018-x
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of theorem-proving procedures
- Title not available (Why is that?)
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- New problems complete for nondeterministic log space
- Space-bounded reducibility among combinatorial problems
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (15)
- On the complexity of graph reconstruction
- For completeness, sublogarithmic space is no space.
- Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets
- Completeness for nondeterministic complexity classes
- DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization
- Collapsing degrees via strong computation
- Complexity results in graph reconstruction
- The relative power of logspace and polynomial time reductions
- On sparseness, reducibilities, and complexity
- Query-monotonic Turing reductions
- Reductions among polynomial isomorphism types
- Space-efficient recognition of sparse self-reducible languages
- Sparse hard sets for P: Resolution of a conjecture of Hartmanis
- Resolution of Hartmanis' conjecture for NL-hard sparse sets
- A note on natural complete sets and Goedel numberings
This page was built for publication: On log-tape isomorphisms of complete sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1249940)
