Low-depth witnesses are easy to find
type: Item
instance of: scholarly article
title: Low-depth witnesses are easy to find
zbMATH Open document ID: 1283.68169
published in: Computational Complexity
publication date: 2012-08-24T00:00:00Z
Mathematics Subject Classification ID: 68Q30
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6072037
zbMATH Keywords: computational depth
zbMATH Keywords: SAT formulas
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: pseudorandom generators
MaRDI profile type: Publication
full work available at URL: s00037-011-0025-1
OpenAlex ID: W2178059285
Wikidata QID: Q62038772
cites work: Computational depth: Concept and applications
cites work: On the Length of Programs for Computing Finite Binary Sequences
cites work: Q4526985
cites work: Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
cites work: Q3238703
cites work: Q3214803
cites work: Q4071737
cites work: An introduction to Kolmogorov complexity and its applications
cites work: Q4788614
cites work: Hardness vs randomness
cites work: A formal theory of inductive inference. Part I
DBLP publication ID: journals/cc/AntunesFPS12
DOI: 10.1007/S00037-011-0025-1
author: Luís Antunes
author: Lance Fortnow
author: Alexandre Pinto
author: André Souto
reviewed by: Ludwig Staiger
description: scientific article; zbMATH DE number 6072037