Computational depth: Concept and applications

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

Autores

antunes, l (Autor) FCUP; fortnow, l (Autor) Outra; van melkebeek, d (Autor) Outra; vinodchandran, nv (Autor) Outra

Ata de Conferência Internacional

Título: THEORETICAL COMPUTER SCIENCE

Páginas: 391-404

14th International Symposium on Fundamentals of Computation Theory

MALMO, SWEDEN, AUG 12-15, 2003

Indexação

ISI Web of Knowledge - 39 Citações

Scopus - 50 Citações

Outras Informações

ID Authenticus: P-004-MA0

DOI: 10.1016/j.tcs.2005.11.033

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: center dot Basic Computational Depth, a clean notion capturing the spirit of Bennett's Logical Depth. We show that a Turing machine M runs in time polynomial on average over the time-bounded universal distribution if and only if for all inputs x, M uses time exponential in the basic computational depth of x. center dot Sublinear-time 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. center dot 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: 14