- Authors: A. Antunes, L. Fortnow, D. van Melkebeek, and N. Vinodchandran.
- Reference: Theoretical Computer Science, 354: 391-404, 2006.
Special issue of for selected papers from
the 14th International Symposium on Fundamentals of Computation Theory.
- Earlier version:
- A. Antunes, L. Fortnow, and D. van Melkebeek.
Computational Depth.
In
Proceedings of the 16th IEEE Conference on Computational
Complexity, pages 266-273, 2001.
Abstract
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. 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.
-
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.
-
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.
