Reducing the complexity of reductions
From MaRDI portal
Publication:5957724
DOI10.1007/s00037-001-8191-1zbMath1052.68052WikidataQ57311713 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
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Unnamed Item, Strong Reductions and Isomorphism of Complete Sets, Unnamed Item, DNF sparsification and a faster deterministic counting algorithm, Local restrictions from the Furst-Saxe-Sipser paper, The isomorphism conjecture for constant depth reductions, Comparing reductions to NP-complete sets, Local reduction, Uniform constant-depth threshold circuits for division and iterated multiplication., Investigations Concerning the Structure of Complete Sets, The Complexity of Complexity, Local Reductions