Isomorphisms and 1-L reductions
From MaRDI portal
Publication:1107310
DOI10.1016/0022-0000(88)90033-5zbMATH Open0652.68041OpenAlexW2170111538MaRDI QIDQ1107310FDOQ1107310
Authors: Eric Allender 
Publication date: 1988
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(88)90033-5
Recommendations
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- Languages that Capture Complexity Classes
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Title not available (Why is that?)
- Number of quantifiers is better than number of tape cells
- On one-one polynomial time equivalence relations
- On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
- Upper and lower bounds for first order expressibility
- Computation times of NP sets of different densities
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- Title not available (Why is that?)
- Collapsing degrees
- Reductions among polynomial isomorphism types
- Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
- Complete problems in the first-order predicate calculus
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (18)
- On one-one polynomial time equivalence relations
- For completeness, sublogarithmic space is no space.
- DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization
- Non-uniform reductions
- Title not available (Why is that?)
- Collapsing degrees via strong computation
- Strong Reductions and Isomorphism of Complete Sets
- Complete Problems and Strong Polynomial Reducibilities
- Length-increasing reductions for PSPACE-completeness
- The degree structure of 1-L reductions
- Reductions among polynomial isomorphism types
- Every polynomial-time 1-degree collapses if and only if P = PSPACE
- Investigations concerning the structure of complete sets
- On growing context-sensitive languages
- Strong reductions and isomorphism of complete sets
- One-way functions and the nonisomorphism of NP-complete sets
- NL-printable sets and nondeterministic Kolmogorov complexity
- Title not available (Why is that?)
This page was built for publication: Isomorphisms and 1-L reductions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1107310)
