Low-depth witnesses are easy to find

DOI10.1007/S00037-011-0025-1zbMATH Open1283.68169DBLPjournals/cc/AntunesFPS12OpenAlexW2178059285WikidataQ62038772 ScholiaQ62038772MaRDI QIDQ445240FDOQ445240

André Souto, Alexandre Pinto, Luís Antunes, Lance Fortnow

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

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

Cites Work

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

Cited In (2)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q445240)