Isomorphisms and 1-L reductions

DOI10.1016/0022-0000(88)90033-5MaRDI QIDQ1107310zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

complete setNP-complete problemsPSPACEp-isomorphismpoly-one functionstrongly invertible function

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3984574
• Polynomial-time isomorphism of 1-L-complete sets
• Reductions among polynomial isomorphism types
• Strong Reductions and Isomorphism of Complete Sets
• Strong reductions and isomorphism of complete sets

Cites work

• scientific article; zbMATH DE number 3841832 (Why is no real title available?)
• scientific article; zbMATH DE number 3984574 (Why is no real title available?)
• scientific article; zbMATH DE number 3695102 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Collapsing degrees
• Complete problems in the first-order predicate calculus
• Computation times of NP sets of different densities
• Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
• Languages that Capture Complexity Classes
• Number of quantifiers is better than number of tape cells
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
• On one-one polynomial time equivalence relations
• Reductions among polynomial isomorphism types
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Upper and lower bounds for first order expressibility

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
• scientific article; zbMATH DE number 5704228 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 3984574 (Why is no real title available?)

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)