Low-Depth Witnesses are Easy to Find

• Tipo: Artigo em Revista Científica Internacional
• Data: 2012

Autores

antunes, l (Autor) FCUP; fortnow, l (Autor) Outra; pinto, a (Autor) Outra; souto, a (Autor) FCUP

Revista

Título: Computational Complexity

Vol. 21

Páginas: 479-497

ISSN: 1016-3328

Editora: Springer Nature

Indexação

ISI Web of Knowledge - 1 Citação

Scopus - 1 Citação

Outras Informações

ID Authenticus: P-002-67X

DOI: 10.1007/s00037-011-0025-1

Abstract (EN): Kolmogorov Complexity measures the amount of information in a string by the size of the smallest program that generates that string. Antunes, Fortnow, van Melkebeek, and Vinodchandran captured the notion of useful information by computational depth, the difference between the polynomial-time-bounded Kolmogorov complexity and traditional Kolmogorov complexity. We show unconditionally how to probabilistically find satisfying assignments for formulas that have at least one assignment of logarithmic depth. The converse holds under a standard hardness assumption though fails if BPP = FewP = EXP. We also prove that assuming the existence of good pseudorandom generators one cannot increase the depth of a string efficiently.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 19