Hardness hypotheses, derandomization, and circuit complexity

DOI10.1007/s00037-008-0241-5zbMath1149.68030OpenAlexW2028946424MaRDI QIDQ937197

A. Pavan, John M. Hitchcock

Publication date: 20 August 2008

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-008-0241-5

zbMATH Keywords

derandomizationCircuit complexityresource-bounded measure and scaled dimension

Mathematics Subject Classification ID

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

Related Items (3)

Unnamed Item ⋮ Nonuniform reductions and NP-completeness ⋮ Autoreducibility of NP-complete sets under strong hypotheses

This page was built for publication: Hardness hypotheses, derandomization, and circuit complexity