Blog personnel d'Arthur Milchior

Je vous ai déjà parlé de P et de NP. Pour rappel, on définit un problème comme une question à laquelle on aimerait pouvoir répondre par oui ou non en fonction de l'entrée. Par exemple, si la question est: «est-ce que le nombre est premier», alors on veut répondre OUI pour 17 et NON pour 18. Même si en vrai, l'entrée serai 10001 et 10010 puisqu'on travaillera en binaire sur un ordinateur.

On s'intéresse au temps, mais aussi à l'espace mémoire. La mémoire, c'est le disque dur - parce qu'au bout d'un certain moment tout ne tient pas en mémoire vive, et qu'il faut bien utiliser des supports à plus long termes. Encore une fois, la question est de savoir, quand l'entrée grandit, à quel vitesse grandissent nos besoins de stockages. Ce n'est pas pareil d'avoir besoin de compter les éléments, d'avoir besoin de recopier l'entrée, ou carrément de recopier tous les sous-ensemble possible des éléments donné en entrée. On parle de PSPACE quand l'espace utilisé est assez petit - i.e. borné par un polynôme en la taille de l'entrée.

Il faut remarquer que tout problème qui peut se résoudre en temps polynomial peut se résoudre en espace polynomial - c'est normal puisque on ne peut juste pas écrire beaucoup de truc en peu de temps. On ne sait par contre pas si le contraire est vrai, si tout ce qui est faisable en espace polynomial l'est en temps polynomial. En fait, ça serait même extrêmement surprenant que ça soit le cas, la communauté informatique est à peu près unanimement^[1] persuadé que PSPACE est beaucoup plus gros que P. Sauf qu'elle n'a aussi aucune idée de comment le montrer.

Il y a quand même une chose qu'on sait, c'est qu'on peut «simplifier» le problème. En tout cas on peut en faire un problème purement mathématique. Purement logique pour être plus précis. Tout ce qui peut se faire en temps polynomial peut se définir à l'aide d'un point fixe inflationnaire. C'est à dire, on prend un ensemble S, qui commence vide, et on rajoute dedans des listes de nombre. Ces listes sont de tailles fixé, et les nombres sont entre 0 et la taille de l'entrée. On rajoute des listes de nombres dans S tant qu'on peut, suivant certaines règles. Et on s'arrête quand on ne peut plus rien rajouter. On peut alors dire que notre problème est satisfait par l'entrée si et seulement si 0,...,0 appartient à cette ensemble.

Les règles pour décider ce qu'on ajoute sont créés à partir des objets suivants, les trois prédicats:

• x<y: qui est vrai si la valeur de x est inférieure à la valeur de y,
• bit(x,y) qui est vrai si le xième bit de y est 1, et
• B(x), qui est vrai si le xième bit de l'entrée est 1,
• S(x1,...,xn) qui est vrai si, en ce moment, la liste x1,...,xn appartient à S\

et puis les connecteurs:

• ... et ...
• ... ou ...,
• non ...,
• pour toute nombre x (entre 0 et la taille de l'entrée), on a...
• il existe un nombre x (entre 0 et la taille de l'entrée), tel que ...,

Ces connecteurs sont ceux de la logique du premier ordre (first-order), on écrit donc que c'est «FO(B,bit,<)». Quand on dit que ces règles sont appliqué pour générer un ensemble par point-fixe inflationnaire (PFI), on note ça «FO(PFI)(B,bit,<)». Il faut remarquer que la règle qui s'applique pour rajouter des éléments petits à petits va donc dépendre de ce qui se trouve, à un instant donné, dans l'ensemble S. C'est pour ça qu'on peut avoir plusieurs étapes, il peut y avoir des éléments que la règle ne dit pas de rajouter au départ, et puis qu'elle dit de rajouter plus tard quand S a grossi.

En gros, l'idée de ces règles est que B permet de lire l'entrée, < permet de compter les éléments (histoire de savoir où on en est dans l'entrée), et bit permet de simuler une étape du calcul. Avec le point fixe, on simule les étapes du calculs jusqu'à ce qu'on finisse le calcul. Et on rajoute 0 dans l'ensemble si à la fin du calcul, l'ordinateur dit qu'il faut accepter. On a donc P=FO(PFI)(B,bit,<).

Le point fixe inflationnaire consiste à ne faire que rajouter des listes de nombres dans l'ensemble. On rajoute des listes de nombres à chaque étape, tant qu'une règle nous disait dans rajouter. On peut aussi considérer un point fixe partiel(PFP), où les règles peuvent aussi demander de retirer des éléments. Il faut juste qu'à un moment, on s'arrête; on ne rajoute rien et on ne retire rien. Et bien avec le point fixe partiel, on peut définir tous les problèmes qui peuvent se résoudre dans PSPACE. On a donc P=FO(PFP)(B,bit,<).

Le fait de ne rajouter des éléments sans les retirer nous forçait a avoir un nombre polynomial d'étape, puisqu'il existe un nombre polynomial de liste d'entiers. En effet la taille de la liste est fixé et que les nombres sont bornés par la tailles de l'entrée. Puisqu'on peut maintenant retirer des objets de l'ensemble, alors on n'est plus contraint par un nombre polynomial d'étape. On est quand même en espace polynomiale, puisqu'on peut représenter tout l'ensemble en espace polynomial.

Ce qu'on peut en conclure, c'est que P=PSPACE si et seulement si le point fixe inflationnaire est équivalent au point fixe partiel quand on a comme prédicats B, < et bit. Autrement dit, P=PSPACE si et seulement si FO(PFI)(B,bit,<)=FO(PFP)(B,bit,<).

Le théorème d'Abiteboul-Vianu indique que FO(PFI)(B,bit,<)=FO(PFP)(B,bit,<) si et seulement si FO(PFI)(B,bit)=FO(PFP)(B,bit).

Bon, ok, écrit comme ça, c'est pas forcément super impressionnant, j'ai supprimé le symbole inférieur des deux côté du signe égal. Voyons donc ce que ça signifie. Si vous vous souvenez de ce que j'ai écrit plus haut, ce symbole, <, c'est ce qui nous permet de regarder les lettres individuellement^[2]. Par exemple, x vaut 0 si et seulement si, il n'existe pas de nombre plus petit que lui, formellement «non(il existe y. y<x)». C'est comme ça qu'on pourra poser des question comme «est-ce que le premier bit de l'entrée est un 0 ou un 1», ou encore, étant donné un bit de l'entrée, regarder son bit successeur. Sans ce prédicat, l'ordre n'a plus d'importance; c'est comme si vous deveniez incapable de distingue 17 de 71. On peut encore faire des calculs, mais pas vraiment de calculs intéressants. Donc c'est très contre intuitif de se dire que l'équation FO(PFI)(B,bit)=FO(PFP)(B,bit) ait seulement du sens. Ou plutôt, même si mathématiquement ça a un sens bien défini, c'est surprenant qu'on puisse en tirer quoi que ce soit.

D'un autre côté, se forcer à ce genre d'algorithme pourrait avoir de vrais avantages. L'ordre est indispensable en informatique pour au minimum une raison: quand on boucle sur la totalité des objets d'un ensemble, on boucle dessus dans un certain ordre. Parfois on peut paralléliser le calcul, et lancer le contenu de la boucle sur autant de processeurs différents qu'il y a d'éléments dans l'ensemble, mais en général ce n'est pas le cas. Et l'ordre peut avoir un effet pervers, par exemple, si c'est l'ordre alphabétique, et que le processus s'arrête durant la boucle, les gens dont le nom de famille est en A seront systématiquement traité, et ceux dont le nom de famille est en Z ne le seront pas. S'interdire ce genre d'ordre éviterait ce problème. Bon, j'ignore à quel point le problème se pose dans les calculs, mais c'est un vrai problème dans la vrai vie académique.

Bref, ce magnifique théorème veut dire qu'on pourrait répondre à l'importante question P=PSPACE, à la question «est-ce que le temps et l'espace, c'est à peu près la même chose en informatique», en décidant d'ignorer totalement la notion d'ordre. Ce qui n'a a priori aucun sens intuitif, aucune raison d'être vrai, mais qui l'est !