scientific article; zbMATH DE number 1559593

zbMATH Open0963.68074MaRDI QIDQ4527042FDOQ4527042

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

Publication date: 1 March 2001

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

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

zbMATH Keywords

complexity class

Mathematics Subject Classification ID

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

Cited In (12)

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

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)