Lance Fortnow (NEC Research Institute):
Computational Depth
We develop a measure of "useful information" that we call computational
depth as the difference of two different Kolmogorov complexity measures. We
believe our measure is simpler and cleaner than previous definitions. We
also get many interesting applications, including:
- We show that if a Boolean formula has satisfying assignments mostly of low
depth, than we can find these witnesses quickly.
- We develop a notion of shallow sets that generalizes sparse and random
sets, and show that any computable set reducible to a shallow set has small
circuits.
- We show that an algorithm is polynomial-time on average for all
"reasonable" distributions if and only for all inputs x, the algorithm runs
in time exponential in the depth of x.
- We explore definitions of "sophistication", the deepest of all strings and
show they exist and encode the halting problem.
This work is based on the two papers below and some additional unpublished
work.
- L. Antunes, L. Fortnow, and D. van Melkebeek. Computational depth. In
Proceedings of the 16th IEEE Conference on Computational Complexity, pages
266-273. IEEE, New York, 2001.
- L. Antunes, L. Fortnow, and V. Vinodchandran. Computational depth vs.
average polynomial time. Technical Report 2001-097, NEC Research Institute,
2001.
Click here for the above two papers. .