Recherche universelle

On doit cet algorithme à Léonid Levin.

L'algorithme de recherche universelle est un algorithme permettant de résoudre tout problème de NP, de manière optimale du moment qu'on ait un vérifieur pour lui.

Une vidéo de l'excellence chaîne polylog

Principe

TBD à écrire propre.

On peut considérer toutes les chaînes de caractères possibles rangées dans l'ordre lexicographique ("a", "b", ..., "z", "aa", ...). On peut toujours écrire une de ces chaines dans un fichier et tenter de l'exécuter avec l'interpréteur python. Si, par chance, on a écrit du code python l'interpréteur va exécuter le code et sinon il va planter.

Si le problème que l'on cherche à résoudre est dans NP on possède un de ses vérifieur et il existe une chaîne de caractères qui correspond à un code python de l'algorithme que le résout de manière optimale. On suppose que ce code est la chaîne en position $L$ dans l'ordre lexicographique.

En prenant une chaîne de caractères en position $L' < L$ que peut-il se passer si on l'exécute avec l'interpréteur python :

cela peut (vraisemblablement) planter rapidement
cela peut exécuter du code avec une complexité plus faible que celle recherchée
cela peut exécuter du code avec une complexité plus forte que celle recherchée
cela peut même boucler indéfiniment

On ne peut donc pas parcourir et exécuter tous les programmes jusqu'à tomber sur celui qui fonctionne (en position $L$ qu'on sait exister mais dont on ne connaît pas la valeur) car cela risque de durer indéfiniment.

L'idée est d'exécuter $k$ opérations des $k$ premières chaînes en vérifiant ensuite si la solution d'un des programme qui s'est arrêter satisfait notre vérifieur. Ci ce n'est pas le cas on recommence en incrémentant $k$.

Au bout d'un moment on aura $k \geq \max(L, C)$ (avec $C$ le nombre d'opération que met notre programme à s'exécuter) et on trouvera notre solution !

On vient de trouver un algorithme universelle pour résoudre tous les problèmes de NP ! Ce n'est pas encore optimal car sa complexité ne va pas être exactement égale à la complexité du meilleur algorithme pour résoudre notre problème.

TBD calcul de la complexité

Exécution fragmenté d'un algorithme

Pour comprendre comment fonctionne la recherche universelle, commençons par étudier l'algorithme suivant, qui prend en paramètre un algorithme A et une de ses entré possible, E :

def exécution_fragmentée(T, A, E):
  I = 1
  tant que I < T:
    exécuter I instructions de A(E)
    Si l'algorithme A s'est arrêté:
      rendre sa sortie
    I = 2 * I

On a la proposition suivante :

Proposition

La complexité d'exécution de l'algorithme exécution_fragmentée est en $\Theta(C(\vert E \vert ))$ où $C(n)$ est la complexité de l'algorithme A

preuve

Supposons que l'algorithme $A(E)$ s'arrête au bout de $K$ instructions. Le nombre maximum d'itération de l'algorithme est alors donné pour exécution_fragmentée(K, A, E)

L'algorithme exécution_fragmentée(T, A, E) sera rentré dans la boucle tant que $\log_2(K)$ fois puisque c'est à ce moment que $I$ sera égal ou plus grand que $K$. Le nombre total d'instructions de l'algorithme exécution_fragmentée(A, E) a alors été :

$$ 1 + 2 + 4 + \dots + 2^i + \dots + 2^{\log_2(K)} $$

C'est à dire que :

les $K/2$ dernières instructions de $A(E)$ ont été exécutées 1 fois
parmi les $K/2$ premières opérations, la moitié ($K/4$) a été exécutée 2 fois (pour les 2 dernières boucles)
parmi les $K/4$ premières opérations, la moitié ($K/8$) a été exécutée 3 fois (pour les 3 dernières boucles)
...
la première opération a été exécuté $\log_2(K)$ fois

Le nombre d'opérations effectuées par l'algorithme est alors :

$$ K\cdot \frac{1}{2} + K\cdot \frac{2}{4} + K\cdot \frac{3}{8} + \dots + K\cdot \frac{i}{2^i} + \dots + K\cdot \frac{\log_2(K)}{2^{\log_2(K)}} = K\cdot (\sum_{1\leq i \leq \log_2{K}}\frac{i}{2^i}) $$

En notant $S_n = \sum_{1\leq i \leq n}$ on a :

$$ \frac{S_n}{2} = S_n - \frac{S_n}{2} = \sum_{1\leq i \leq n }\frac{1}{2^i} = 1- \frac{1}{2^n} $$

Et donc $S_n \leq S_{\infty} = 2$ ce qui nous permet de conclure que le nombre d'opérations total est $2K$, ce qui conclut la preuve.

Exécution fragmentée générale

L'algorithme de la recherche universelle va procéder un peu de la même manière que celui d'exécution fragmentée mais pour tous les algorithmes.

Un pseudo-code étant un texte, on peut considérer tous les textes rangés par ordre lexico-graphique. On peut tenter d'exécuter chaque texte comme un pseudo-code et voir ce qu'il se passe. Exécuter $K$ instructions d'un de ces texte peut résulter en 3 cas :

un plantage (ce n'est pas un pseudo-code on tente d'exécuter quelque chose qui n'est pas une instruction, on fait une instruction interdite comme une division par zéro par exemple, etc)
le texte est un pseudo-code valide et on a exécuté entièrement son code.On peut récupérer sa sortie.
le texte est un pseudo-code valide (au moins pour les $K$ instructions) mais il ne s'est pas arrêté : il tourne toujours après $K$ instructions.

On considère alors l'algorithme next(B) qui, rend la chaîne $B'$ qui suit la chaîne $B$ dans l'ordre lexico-graphique.

def exécution_fragmentée_universelle(A, E):
  I = 1
  tant que VRAI:
    B = ""
    tant que I ≥ 1:
      B = next(B)
      exécuter I instructions de B(E)
      Si on s'est arrêté et que B == A:
        rendre sa sortie
      I = I / 2
    I = 2 * I

Proposition

La complexité d'exécution de l'algorithme exécution_fragmentée_universelle est en $\Theta(C(\vert E \vert ))$ où $C(n)$ est la complexité de l'algorithme A

preuve

Supposons que l'algorithme $A(E)$ s'arrête au bout de $K$ instructions et que la chaîne de caractère qui correspond à son pseudo-code soit en position $L$ de la liste ordonnée de tous les textes.

L'algorithme exécution_fragmentée_universelle va s'arrêter lorsqu'il aura effectué $K$ opération de l'algorithme $A$

Tout se passe alors comme si :

on avait exécuté exécution_fragmentée(K2**L, A1, E) pour A1, le premier élément de la liste ordonnée des textes
on avait exécuté exécution_fragmentée(K2**(L-1), A2, E) pour A2, le second élément de la liste ordonnée des textes
...
on avait exécuté exécution_fragmentée(K, AL, E) pour AL, le $L$ ème élément de la liste ordonnée des textes
on avait exécuté exécution_fragmentée(K/2, A(L+1), E) pour A(L+1), le $L+1$ ème élément élément de la liste ordonnée des textes
...
on avait exécuté exécution_fragmentée(1, A(L+1), E) pour A(L+log(K)), le $L+\log_2(K)$ ème élément élément de la liste ordonnée des textes.

La complexité maximale est alors :

$$ \begin{array}{lcl} 2 \cdot 2^L\cdot K + 2 \cdot 2^{L-1} \cdot K + \dots + 2 \cdot 2^{0} \cdot K + 2 \cdot \frac{1}{2} \cdot K + \dots + 2 \cdot \frac{1}{2^i} \cdot K + \dots + 2 \cdot \frac{1}{2^{\log_2(K)}} \cdot K&=&\\ 2\cdot(2^{L+1}-1)\cdot K + 2\cdot (1-\frac{1}{2^{\log_2(K)}})\cdot K&\leq&\\ 2^{L+2}\cdot K \end{array} $$

Comme $L$ est une constante, on a bien le résultat demandé

On voit que la complexité asymptotique est la même que celle de l'algorithme initial. Ce qui change c'est la constante multiplicative, $2^{L+2} qui peut être gigantesque !

Recherche universelle

L'algorithme de recherche universelle est une variation de l'algorithme précédent pour les problèmes de NP. Soit $P$ un problème de NP et $v$ un de ses vérificateurs.

On alors l'algorithme :

def recherche_universelle(v, E):
  I = 1
  tant que VRAI:
    B = ""
    tant que I ≥ 1:
      B = next(B)
      exécuter I instructions de B(E)
      Si B(E) s'est arrêté et que v(B(E), E) est vrai:
        rendre sa sortie
      I = I / 2
    I = 2 * I

Proposition

La complexité d'exécution de l'algorithme recherche_universelle est en $\Theta(C(\vert E \vert ) + \log_2(C(\vert E \vert )) \cdot D(\vert E \vert ))$ où :

$C(n)$ est la complexité minimale d'un algorithme résolvant $P$
$D(n)$ est la complexité du vérifieur $v$

preuve

Idem que la preuve précédente. Il faut juste ajouter qu'il faut vérifier chaque pseudo-code (il y en a $L+ \log_2(C(\vert E \vert ) ))$ qui s'arrête une fois.

Dans de très nombreux cas, $D(n)$ est petite devant $C(n)$, par exemple si $D(n) = \Theta(n^a)$ et $C(n) = \Theta(n^b)$ avec $b>a$ puisqu'asymptotiquement $\frac{n^{\epsilon}}{\ln(n)}$ tend vers l'infini. Et on peut négliger le terme en $D(n)$, ce qui donne un algorithme optimal pour résoudre tout problème de NP !

Donc si $P = NP$ alors la recherche universelle est l'algorithme optimal qui résout tout. Bien sur l'arnaque se situe au niveau de la constante multiplicative, $2^L$ qui peut être gigantesque ce qui fait que même si asymptotiquement le résultat est optimal ce n'est pas le cas dans des cas d'utilisation normale des algorithme. La recherche universelle n'est donc pas une excuse pour ne pas chercher l'algorithme le plus efficace pour résoudre un problème.