Applications de complexité de Kolmogorov en complexité de calcul

De manière informelle, la complexité de Kolmogorov d'une chaîne est la longueur d'un programme le plus court qui génère x . Nous pouvons définir une notion de 'chaîne aléatoire' en l'utilisant ( x est aléatoire si K ( x ) ≥ 0,99 | x | ) Il est facile de voir que la plupart des chaînes sont aléatoires (il n'y a pas autant de programmes courts).$x$$x$$x$$K(x) \geq 0.99 |x|$

La théorie de la complexité de Kolmogorov et la théorie de l'information algorithmique sont assez développées de nos jours. Et il existe plusieurs exemples amusants d'utilisation de la complexité de Kolmogorov dans des démonstrations de différents théorèmes qui ne contiennent rien dans la déclaration de la complexité de Kolmogorov ( LLL constructive , inégalité de Loomis-Whitney , etc.).

Existe-t-il des applications intéressantes de la complexité de Kolmogorov et de la théorie de l'information algorithmique dans la complexité de calcul et les domaines connexes ? Je pense qu'il devrait y avoir des résultats utilisant la complexité de Kolmogorov comme un simple remplacement des arguments de comptage simples. Ce n’est bien sûr pas intéressant.

Lance Fortnow a écrit un article sur ce sujet: Complexité de Kolmogorov et complexité informatique

Vous devriez également consulter Une introduction à la complexité de Kolmogorov et à ses applications par Li et Vitanyi, le livre de référence sur le sujet. En particulier, le chapitre 6 "La méthode d'incompressibilité" traite d'un certain nombre d'applications complexes, telles que la preuve de complexité de Kolmogorov du lemme de commutation de Hastad (tiré de Circuit Lower Bounds à la Kolmogorov de Fortnow et Laplante).

Et il y a des applications dans la complexité de la communication (par exemple, Complexité de Kolmogorov et méthodes combinatoires dans la complexité de la communication de Kaplan et Laplante).

Il y a quelques jours à peine, Scott Aaronson a utilisé un argument fondé sur la complexité de Kolmogorov pour montrer l' équivalence de l'échantillonnage et de la recherche . En outre, il fait valoir que, dans son argument, la complexité de Kolmogorov est utilisée de manière essentielle, ce qui ne constitue pas simplement un raccourci pour un argument de comptage.

Ce résultat de Alon et al. peut être obtenu par le biais de la complexité de Kolmogorov.

$\mathrm{poly}(\log |E|)$

Un excellent article que je connaisse (en plus de ceux qui sont mentionnés dans d’autres réponses):

Juris Hartmanis, Complexité généralisée de Kolmogorov et structure des calculs réalisables , FOCS 1983.

La principale chose dont je me souviens de ce document est la construction d’un oracle séparant P de NP basée sur la complexité de Kolmogorov.

Un autre papier qui me vient à l’esprit est

Allender et al., Power from Random Strings , FOCS 2002 ( version ECCC ) et SICOMP 2006 .

Si je me souviens bien, ce dernier document sépare la complétude de Turing en temps polynomial de la complétude plusieurs-un pour log-space dans PSPACE, en utilisant des arguments de complexité de Kolmogorov. Bien sûr, cela fait beaucoup d'autres choses, mais je me souviens de cette séparation étant une application qui présente un intérêt indépendant en dehors de la théorie algorithmique de l'information.

Il existe également une technique de limite inférieure quantique qui utilise la complexité de Kolmogorov:

" Limites inférieures de la complexité des requêtes aléatoires et quantiques utilisant des arguments de Kolmogorov " par Sophie Laplante et Frédéric Magniez

$s$$K(s)$

(Maintenant, passons au sérieux.) Daniil Musatov a récemment montré qu'une dérandomisation naïve peut fournir des constructions raisonnables pour des objets dont l'existence est généralement démontrée de manière non constructive via la méthode probabiliste. Je pense que cela est susceptible de fournir d’importantes applications futures de la complexité de Kolmogorov, liée aux ressources, à la complexité de calcul.

• Daniil Musatov, Améliorer la version du théorème de complexité conditionnelle de Muchnik dans l'espace-borné via la «dénormalisation naïve» , RSE 2011, LNCS 6651, 64–76. doi: 10.1007 / 978-3-642-20712-9_6 ( pré-impression )

Voir aussi les articles citant celui-ci .

(Edit: lien vers la version publiée la plus récente.)

H. Buhrman, L. Fortnow et S. Laplante. La complexité de Kolmogorov liée aux ressources revisitée. SIAM Journal on Computing, 31 (3): 887-905, 2002. ( journal , page Web de Lance ).

Inclut des applications de complexité de Kolmogorov telles que:

• Une preuve de Valiant-Vazirani
• Des assignations satisfaisantes de formules booléennes peuvent être énumérées en polynômes temporels dans la taille de sortie si et seulement si une assignation unique peut être trouvée rapidement
• Une nouvelle preuve que BPP est dans Sigma_2 P
• Plusieurs constructions d'oracle

Certains de ces éléments ont d'abord été prouvés dans cet article, tandis que d'autres sont simplement de nouvelles preuves d'anciens théorèmes, utilisant la complexité de Kolmogorov.

Les applications de la complexité de Kolmogorov, limitée dans le temps, dans la théorie de la complexité constituent une étude intéressante réalisée par Eric Allender sur d'autres applications. Bien que de nombreux résultats résultent en des implications, certaines sont de véritables applications, telles que:

• Cor 13: Par rapport à un oracle générique, il n’existe aucun générateur pseudo-aléatoire sûr contre les adversaires P / poly.
• Thm 16 [Allender et Gore, 1991]: Il existe un oracle par rapport auquel tous les prédicats de NE peuvent être résolus en temps exponentiel et E = Union_k \ Sigma_k-TIME (n).

Les deux preuves utilisent la complexité de Kolmogorov de manière significative.

$D$$D$

La longueur minimale de description utilise la complexité de Kolmogorov (ou ses approximations et généralisations dues à l’indécidabilité) dans l’apprentissage théorique-information et la théorie de l’inférence. Plus précisément, MDL est utilisé pour trouver des explications de données qui évitent naturellement les surajustements.

Jorma Rissanen fournit une bonne introduction à son concept: http://www.mdl-research.org/jorma.rissanen/pub/Intro.pdf

Voulez-vous dire quelque chose comme ça, ilyaraz?

http://arxiv.org/abs/1004.3993