On log-tape isomorphisms of complete sets
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3532523 (Why is no real title available?)
- scientific article; zbMATH DE number 3560737 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 3586493 (Why is no real title available?)
- New problems complete for nondeterministic log space
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Space-bounded reducibility among combinatorial problems
- The complexity of theorem-proving procedures
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)
