Reducing the complexity of reductions

DOI10.1007/S00037-001-8191-1MaRDI QIDQ5957724zbMATH OpenOpenAlexDBLPWikidataFDO

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

Publication date 5 May 2002

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-001-8191-1

zbMATH Keywords

Berman-Hartmanis conjecturepowering in finite fields

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 1559593
• scientific article; zbMATH DE number 2081095
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• Polynomial-time isomorphism of 1-L-complete sets
• The isomorphism conjecture for NP

Cited in

(22)

• scientific article; zbMATH DE number 1559593 (Why is no real title available?)
• Lazy narrowing with simplification
• Reducing sequences
• The Complexity of Complexity
• Comparing reductions to NP-complete sets
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Local reduction
• Non-uniform reductions
• A reduction algorithm meeting users' requirements.
• Reductivity
• Rudimentary reductions revisited
• Strong Reductions and Isomorphism of Complete Sets
• scientific article; zbMATH DE number 7528580 (Why is no real title available?)
• scientific article; zbMATH DE number 7650112 (Why is no real title available?)
• DNF sparsification and a faster deterministic counting algorithm
• Investigations concerning the structure of complete sets
• scientific article; zbMATH DE number 1222831 (Why is no real title available?)
• Local restrictions from the Furst-Saxe-Sipser paper
• Finding Reductions Automatically
• The isomorphism conjecture for constant depth reductions
• Nonuniform reductions and NP-completeness
• Local reductions

This page was built for publication: Reducing the complexity of reductions

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