4
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ It would be nicer if you linked a resource you trust. $\endgroup$ – Raphael Jul 18 '12 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$ – Kaveh Jul 18 '12 at 3:42
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.