scientific article; zbMATH DE number 3984574

MaRDI QIDQ3747726zbMATH OpenFDO

Authors Eric Allender

Publication date 1986

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

• Isomorphisms and 1-L reductions
• The degree structure of 1-L reductions
• Polynomial-time isomorphism of 1-L-complete sets
• Reductions among polynomial isomorphism types
• Complete Problems and Strong Polynomial Reducibilities

Cited in

(11)

• Collapsing degrees
• scientific article; zbMATH DE number 5704228 (Why is no real title available?)
• 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
• Every polynomial-time 1-degree collapses if and only if P = PSPACE
• On the isomorphism conjecture for weak reducibilities
• Strong reductions and isomorphism of complete sets
• Isomorphisms and 1-L reductions
• Complete problems and strong polynomial reducibilities

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3747726)