Low-depth witnesses are easy to find

DOI10.1007/s00037-011-0025-1zbMath1283.68169WikidataQ62038772 ScholiaQ62038772MaRDI QIDQ445240

J. Herrera, H. S. Yoon

Publication date: 24 August 2012

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

Full work available at URL: https://doi.org/10.1007/s00037-011-0025-1

zbMATH Keywords

Kolmogorov complexity; pseudorandom generators; computational depth; SAT formulas

Mathematics Subject Classification ID

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

03D15: Complexity of computation (including implicit computational complexity)

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