On log-tape isomorphisms of complete sets

DOI10.1016/0304-3975(78)90018-XzbMath0387.68035OpenAlexW2043113327MaRDI QIDQ1249940

Juris 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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (15)

Reductions among polynomial isomorphism types ⋮ Collapsing degrees via strong computation ⋮ Space-efficient recognition of sparse self-reducible languages ⋮ Completeness for nondeterministic complexity classes ⋮ Query-monotonic Turing reductions ⋮ DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization ⋮ Complexity results in graph reconstruction ⋮ On the complexity of graph reconstruction ⋮ A note on natural complete sets and Goedel numberings ⋮ On sparseness, reducibilities, and complexity ⋮ Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets ⋮ Sparse hard sets for P: Resolution of a conjecture of Hartmanis ⋮ Resolution of Hartmanis' conjecture for NL-hard sparse sets ⋮ For completeness, sublogarithmic space is no space. ⋮ The relative power of logspace and polynomial time reductions

Cites Work

• Space-bounded reducibility among combinatorial problems
• New problems complete for nondeterministic log space
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• The complexity of theorem-proving procedures
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On log-tape isomorphisms of complete sets