A Reader's Question about Kolmogorov Complexity

My first question from a reader:

I'm interested in Kolmogorov complexity and its relationship to traditional computational complexity theory. It seems that NP-complete problems all have a pretty low Kolmogorov complexity, so in this sense it seems KC will not serve as a good measure for problem instance hardness. I would like to know what you would say on this topic sometime in the future.

Andrei Nikolaevich Kolmogorov was born on April 25, 1903 and in 2003 there will be several events to mark the 100th anniversary of his birth. I plan to devote several posts next year to mark these events and discuss Kolmogorov complexity. If you cannot wait, I recommend the great textbook on the topic, An Introduction to Kolmogorov Complexity and Its Applications by Ming Li and Paul Vitányi.

As to the reader's question, initial segments of any computable set, including the NP-complete sets, have low Kolmogorov complexity and are not much use to measure the computational complexity of that set. However, one can use time-bounded Kolmogorov complexity to capture computational complexity.

Let p be a t-good program for a set A if for all inputs x, p(x) uses t(|x|) time and says "Yes", "No" or "I don't know". If p(x) says Yes then x is in A and if p(x) says "No" then x is not in A.

We define the t-time-bounded instance complexity of an instance x of a set A as

ic^t(x:A) = min{|p| : p is a t-good program for A and p(x) ≠ "I don't know"}

We have that A is in P if and only if there is a constant c and a polynomial q such that for all x, ic^q(x:A)≤ c. To prove P ≠ NP one only needs to that ic^q(x:SAT) is unbounded for all polynomials q.

For more information about instance complexity see Section 7.4 of Li and Vitányi.