Computational depth

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

Authors

antunes, l (Author) FEP; fortnow, l (Author) Other; van melkebeek, d (Author) Other

Conference proceedings International

Title: 16TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS

Pages: 266-273

16th Annual IEEE Conference on Computational Complexity

CHICAGO, IL, JUN 18-21, 2001

Indexing

ISI Web of Knowledge - 0 Citations

Scopus - 6 Citations

Other information

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

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 8