Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds

DOI10.1007/11672142_37zbMath1136.68403OpenAlexW1959592988MaRDI QIDQ5449821

Harry Buhrman, Falk Unger, Leen Torenvliet

Publication date: 19 March 2008

Published in: STACS 2006 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11672142_37

zbMATH Keywords

Computational ComplexitySparsenessSelfreducibility

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

This page was built for publication: Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds