scientific article; zbMATH DE number 1559593

MaRDI QIDQ4527042zbMATH OpenFDO

Authors Russell Impagliazzo, Toniann Pitassi, Steven Rudich, Manindra Agrawal, Eric Allender

Publication date 1 March 2001

zbMATH Keywords

complexity class

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Reducing the complexity of reductions
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• Nonuniform reductions and NP-completeness
• Reductions among polynomial isomorphism types
• The isomorphism conjecture for constant depth reductions

Cited in

(12)

• A reduction algorithm meeting users' requirements.
• Finding Reductions Automatically
• Lazy narrowing with simplification
• A lower bound for primality
• For completeness, sublogarithmic space is no space.
• Nonuniform reductions and NP-completeness
• The descriptive complexity approach to LOGCFL
• Reducing the complexity of reductions
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• Reductivity
• Value-free reductions
• scientific article; zbMATH DE number 1222831 (Why is no real title available?)

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 Q4527042)