Computational depth

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

Autores

antunes, l (Autor) FEP; fortnow, l (Autor) Outra; van melkebeek, d (Autor) Outra

Ata de Conferência Internacional

Título: 16TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS

Páginas: 266-273

16th Annual IEEE Conference on Computational Complexity

CHICAGO, IL, JUN 18-21, 2001

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 6 Citações

Outras Informações

ID Authenticus: P-007-9H6

DOI: 10.1109/ccc.2001.933893

Abstract (EN): We introduce Computational Depth, a measure for the amount of "nonrandom" or "useful" information in a string by considering the difference of various Kolmogorov complexity measures. We investigate three instantiations of Computational Depth: Basic Computational Depth, a clean notion capturing the spirit of Bennett's Logical Depth. Time-t Computational Depth and the resulting concept of Shallow Sets, a generalization of sparse and random sets based on low depth properties of their characteristic sequences. We show that every, computable set that is reducible to a shallow set has polynomial-size circuits. Distinguishing Computational Depth, measuring when strings are easier to recognize than to produce. We show that if a Boolean formula has a nonnegligible fraction of its satisfying assignments with low depth, then we can find a satisfying assignment efficiently.

Idioma: Inglês

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

Nº de páginas: 8