scientific article; zbMATH DE number 3984574

MaRDI QIDQ3747726zbMATH OpenFDO

Authors Eric Allender

Publication date 1986

zbMATH Keywords

complete setNP-complete problemsp-isomorphismpoly-one functionPSPACEstrongly invertible function

Mathematics Subject Classification ID

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

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

(12)

• Isomorphisms and 1-L reductions
• Collapsing degrees
• Polynomial-time isomorphism of 1-L-complete sets
• On the isomorphism conjecture for weak reducibilities
• Length-increasing reductions for PSPACE-completeness
• scientific article; zbMATH DE number 5704228 (Why is no real title available?)
• Complete Problems and Strong Polynomial Reducibilities
• Complete problems and strong polynomial reducibilities
• The degree structure of 1-L reductions
• Strong reductions and isomorphism of complete sets
• Every polynomial-time 1-degree collapses if and only if P = PSPACE
• Strong Reductions and Isomorphism of Complete Sets

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)