Reducing the complexity of reductions

DOI10.1007/S00037-001-8191-1zbMATH Open1052.68052DBLPjournals/cc/AgrawalAIPR01OpenAlexW2066938865WikidataQ57311713 ScholiaQ57311713MaRDI QIDQ5957724FDOQ5957724

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

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

zbMATH Keywords

Berman-Hartmanis conjecturepowering in finite fields

Mathematics Subject Classification ID

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

Cited In (22)

• Title not available (Why is that?)
• 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
• Strong Reductions and Isomorphism of Complete Sets
• Rudimentary reductions revisited
• Title not available (Why is that?)
• Title not available (Why is that?)
• DNF sparsification and a faster deterministic counting algorithm
• Investigations concerning the structure of complete sets
• Title not available (Why is that?)
• Finding Reductions Automatically
• Local restrictions from the Furst-Saxe-Sipser paper
• 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)