Reducing the complexity of reductions

DOI10.1007/s00037-001-8191-1zbMath1052.68052OpenAlexW2066938865WikidataQ57311713 ScholiaQ57311713MaRDI QIDQ5957724

Russell Impagliazzo, Steven Rudich, Eric W. Allender, Manindra Agrawal, Toniann Pitassi

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)

Related Items (12)

Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ Local Reductions ⋮ Local reduction ⋮ DNF sparsification and a faster deterministic counting algorithm ⋮ Comparing reductions to NP-complete sets ⋮ The isomorphism conjecture for constant depth reductions ⋮ Unnamed Item ⋮ The Complexity of Complexity ⋮ Local restrictions from the Furst-Saxe-Sipser paper ⋮ Unnamed Item ⋮ Strong Reductions and Isomorphism of Complete Sets ⋮ Investigations Concerning the Structure of Complete Sets

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