Low-depth witnesses are easy to find

DOI10.1007/s00037-011-0025-1zbMath1283.68169DBLPjournals/cc/AntunesFPS12OpenAlexW2178059285WikidataQ62038772 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 complexitypseudorandom generatorscomputational depthSAT formulas

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Information measures for infinite sequences ⋮ On the Optimal Compression of Sets in PSPACE

Cites Work

• Hardness vs randomness
• Computational depth: Concept and applications
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• On the Length of Programs for Computing Finite Binary Sequences
• A formal theory of inductive inference. Part I
• An introduction to Kolmogorov complexity and its applications
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Low-depth witnesses are easy to find