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?
2 Answers
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
-
1$\begingroup$ It would be nicer if you linked a resource you trust. $\endgroup$– RaphaelCommented Jul 18, 2012 at 1:33
-
1$\begingroup$ @Raphael, the standard reference for Kolmogorov complexity is Li and Vitanyi, though I don't have a copy with me to check if it covers the infinite words case. There are lots of papers on algorithmic randomness but I don't remember a good reference right now that I am sure about it covering the topic. It would probably be better to post a reference-request question asking for a survey/book on this topic. $\endgroup$– KavehCommented Jul 18, 2012 at 3:42
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.