Kolmogorov complexity of a decision problem

Question

What's the definition of Kolmogorov complexity for a decision problem? For example, how to define the length of the shortest program that solves the 3SAT problem? Is it the "smallest" Turing machine that recognizes the 3SAT langauge?

Answer 1

We can view of a language $A$ as an infinite binary string (the infinite binary string corresponding to the characteristic function of $A$) and then use the notion of Kolmogorov complexity for such strings.

Google for: Kolmogorov complexity infinite words

Answer 2

Like Kaveh said, you can view a decision problem as a language consisting of the descriptions of all the "yes" instances. Then the Kolmogorov complexity of the language is, as you said, the length of the smallest program that produces all those descriptions.

How we describe the program that generates the instances (and hence defines the Kolmogorov complexity) is in a sense a matter of agreement. To do it we first pick a universal description language which we will use describe all languages. Exactly what this universal language is however is somehow not that interesting. Turing Machines are a possible choice, however the Kolmogorov complexity of a string is in general incomputable, so the precise encoding language is less interesting than the more general implications that are true for any reasonable encoding.