Computational depth: Concept and applications

• Type: Article in International Conference Proceedings Book
• Date: 2006

Authors

antunes, l (Author) FCUP; fortnow, l (Author) Other; van melkebeek, d (Author) Other; vinodchandran, nv (Author) Other

Conference proceedings International

Title: THEORETICAL COMPUTER SCIENCE

Pages: 391-404

14th International Symposium on Fundamentals of Computation Theory

MALMO, SWEDEN, AUG 12-15, 2003

Indexing

ISI Web of Knowledge - 39 Citations

Scopus - 50 Citations

Other information

Authenticus ID: 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 14