Kolmogorov complexity of a decision problem 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?
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