scientific article; zbMATH DE number 3984574

zbMATH Open0608.68036MaRDI QIDQ3747726FDOQ3747726

Authors: Eric Allender 

Publication date: 1986

Title of this publication is not available (Why is that?)

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

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)

Cited In (11)

• Collapsing degrees
• Title not available (Why is that?)
• 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
• Strong reductions and isomorphism of complete sets
• On the isomorphism conjecture for weak reducibilities
• 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)