Low-depth witnesses are easy to find

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2007

Autores

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

Ata de Conferência Internacional

Título: ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY

Páginas: 46-51

22nd Annual IEEE Conference on Computational Complexity

San Diego, CA, JUN 13-16, 2007

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 3 Citações

Outras Informações

ID Authenticus: P-004-ERF

DOI: 10.1109/ccc.2007.13

Abstract (EN): Antunes, Fortnow, van Melkebeek and Vinodchandran captured the notion of non-random 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 show that assuming 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: 6