Kolmogorov complexité d'un problème de décision

Question

Quelle est la définition de la complexité de Kolmogorov pour un problème de décision? Par exemple, comment définir la longueur du programme le plus court qui résout le problème de 3SAT? Est-ce la "plus petite" machine de Turing qui reconnaît le langauge 3SAT?

Answer 1

Nous pouvons voir d'une langue $ A $ comme une chaîne binaire infinie (la chaîne binaire infinie correspondant à la fonction caractéristique de $ A $), puis utiliser la notion de complexité de Kolmogorov pour ces chaînes.

Google pour: la complexité de Kolmogorov mots infinis

Answer 2

Comme Kaveh dit, vous pouvez voir un problème de décision en tant que langue comprenant les descriptions de toutes les instances « oui ». Ensuite, la complexité de Kolmogorov de la langue est, comme vous le dites, la longueur du programme le plus petit qui produit toutes ces descriptions.

Comment nous décrivons le programme qui génère les instances (et définit donc la complexité de Kolmogorov) est en quelque sorte une question d'un accord. Pour ce faire nous avons d'abord choisir un langage de description universelle que nous utiliserons décrire toutes les langues. Exactement ce que ce langage universel est cependant est en quelque sorte pas intéressant. Les machines de Turing sont un choix possible, mais la complexité de Kolmogorov d'une chaîne est en général incompressible, de sorte que le langage précis de codage est moins intéressant que les implications plus générales qui sont vraies pour tout encodage raisonnable.