Isomorphisms and 1-L reductions

DOI10.1016/0022-0000(88)90033-5zbMath0652.68041OpenAlexW2170111538MaRDI QIDQ1107310

Eric W. 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

zbMATH Keywords

NP-complete problemscomplete setPSPACEp-isomorphismpoly-one functionstrongly invertible function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Collapsing degrees via strong computation ⋮ NL-printable sets and nondeterministic Kolmogorov complexity ⋮ One-way functions and the nonisomorphism of NP-complete sets ⋮ DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization ⋮ The degree structure of 1-L reductions ⋮ Non-uniform reductions ⋮ Strong Reductions and Isomorphism of Complete Sets ⋮ On growing context-sensitive languages ⋮ Investigations Concerning the Structure of Complete Sets ⋮ For completeness, sublogarithmic space is no space.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On one-one polynomial time equivalence relations
• Complete problems in the first-order predicate calculus
• Reductions among polynomial isomorphism types
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• Collapsing degrees
• Number of quantifiers is better than number of tape cells
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• 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
• Languages that Capture Complexity Classes
• Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
• On Isomorphisms and Density of $NP$ and Other Complete Sets