Systèmes interactifs pour la résolution de problèmes complexes

Master 2 recherche : systèmes et logiciels

Date : 8 juillet 2009

Encadrants :

Jean-Louis Roch Pierre-François Dutot

Jury :

Jean-Claude Fernandez

Jérôme Euzenat Eric Gaussier

Projet présenté par Marin Bougeret et réalisé au laboratoire ID (LIG)

Remerciements

Je tiens à remercier tout particulièrement Monsieur Pierre-François Dutot et Monsieur Jean-Louis Roch pour leur précieux conseils et pour le temps qu’ils m’ont accordé cette année. Je les remercie également pour la confiance qu’ils m’ont accordée tout au long du stage.

Je ne pourrais non plus oublier Jean-Denis Lesage pour sa patience et sa disponibilité, Erik Saule pour le temps passé à réfléchir ensemble, Feryal-Kamila Moulaï pour toutes nos discussions, et tous les autres !

Table des matières

Introduction 1 1. Présentation du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2. État de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 3. Approche proposée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 4. Justification du problème pratique choisi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 5. Présentation du document . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

I Systèmes interactifs et théorie de la complexité 4

Introduction de la partie théorique 5

1 Étude d’un modèle d’interactivité : PCP 6

1.1. Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1..1 Rappels sur P et NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1..2 L’oracle et l’aléa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1..3 Définition de PCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.2. Propriétés de PCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2..1 Résultats immédiats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2..2 Démonstration d’un résultat analogue au théorème PCP . . . . . . . . . . . . . . . . . 10

1.3. Le théorème PCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.3..1 Les résultats obtenus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.3..2 Un peu d’histoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.4. Conséquences du théorème PCP sur l’inapproximabilité . . . . . . . . . . . . . . . . . . . . . 18

2 D’autres modèles de preuve interactive 20

2.1. Les protocoles d’Arthur et Merlin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.1..1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.1..2 Propriétés simples des classes Arthur-Merlin . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1..3 Des résultats plus forts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.2. IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.3. Liens entre ces classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4. Le problème des graphes non-isomorphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3 Le problème du puzzle 23 3.1. Définition formelle du problème d’optimisation combinatoire associé . . . . . . . . . . . . . . 23 3.2. Puzzle est compliqué (3-partition se réduit à puzzle) . . . . . . . . . . . . . . . . . . . . . . . 24 3.3. Utilité de l’intéractivité pour Puzzle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

II Un framework général pour l’intéractivité et une implémentation 26

4 Comment concevoir l’intéractivité 27 4.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2. Les objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.3. Les types de problèmes que l’on veut résoudre interactivement . . . . . . . . . . . . . . . . . 27 4.4. Modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

4.4..1 Une difficulté pour définir l’état . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.4..2 Définition du modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.4..3 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5 Spécification d’un modèle pratique ou Vers la pratique 30 5.1. Quand doit-on pouvoir agir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.2. Définition d’un état en pratique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.3. f_{oracle} en pratique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

5.3..1 La nature de f_{oracle} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.3..2 Définir f_{oracle} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5.4. Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

6 Instanciation du modèle pour le problème du puzzle 33

6.1. Présentation de l’implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6.1..1 Structure générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6.1..2 Côté calculateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6.1..3 Côté oracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 6.1..4 Interface entre les deux parties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

6.2. Les difficultés liées à l’interprétation des résultats . . . . . . . . . . . . . . . . . . . . . . . . . 34 6.3. Mesures d’un test simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

7 Perspectives et conclusion 37

Introduction

1. Présentation du problème

On entend souvent dire que les machines sont bêtes. En effet, bien que la puissance de celles-ci ne cesse d’augmenter, elles ne se rapprochent pas particulièrement d’une façon humaine et «intelligente» d’agir. Depuis longtemps, avec par exemple Turing et son «test de Turing», la comparaison entre l’intelligence humaine et la machine est discutée. La problématique de «l’interaction» vise à pouvoir faire profiter aux deux parties des deux formes d’intelligence.

Lorsque l’on envisage en pratique l’interaction entre un calculateur et un oracle, une constatation vient tout de suite à l’esprit : l’interaction semble dissymétrique, au sens ou l’une des entité va effectuer un calcul conséquent, et l’autre va se contenter de lui fournir quelques informations pour l’y aider. Nous nous sommes intéressé dans ce rapport au cas ou l’oracle est humain, et ou le calculateur est donc la machine. L’humain fonctionnant en «boîte noire», et fournissant des indications.

Il existe déjà de nombreux travaux visant à profiter de l’interaction avec un expert extérieur. Il convient donc de commencer par examiner quels sont les différents types d’objectifs, de problématiques, et de moyens que l’on peut rencontrer dans le domaine des systèmes interactifs, afin de comprendre l’approche particulière qui sera présentée dans ce rapport.

2. État de l’art

Quelle que soit le type d’approche considérée, une hypothèse commune est présente : l’expert (en général humain) a une connaissance supplémentaire dont on veut profiter. Les différences apparaissent donc plutôt selon la nature du problème à résoudre ou la façon dont on va exploiter l’expert.

Un premier domaine ayant suscité l’interaction est la fouille de données. En effet, les problèmes liés à l’exploitation de gros volumes de données (en particulier dans le domaine de la médecine [?]) se prêtent bien à l’utilisation de connaissance extérieure : l’utilisateur veut par exemple cibler les données les «plus» intéressantes, trouver des motifs permettant une meilleure interprétation. Cependant nous ne détaillerons pas l’existant de ce domaine, car notre but ici n’est pas la fouille de données.

D’autre part, pour ce qui est de la résolution de problèmes en coopération système-utilisateur ([?]), une constante apparaît aussi : de nombreuses méthodes s’appuient sur les systèmes à base de connaissance (SBC). Le but de ces coopérations système-utilisateur ressemble à priori au notre, on veut accélérer la résolution d’un problème grâce à l’intéractivité, tout en trouvant un compromis «souple» permettant à la fois l’autonomie du système et la possibilité de diriger le processus de résolution. Cependant, les problématiques ne sont pas les mêmes que les nôtres. En effet, rappelons que par définition d’un SBC, le but est que le calculateur résonne comme un humain. On veut lui inculquer une façon de raisonner, afin qu’il soit capable de résoudre toute instance d’un problème donné. On se heurte donc aux problèmes classiques, type «IA», de représentation de connaissances, de raisonnements, car on veut par exemple ([]) que le raisonnement du système soit compréhensible par l’utilisateur, et que ce dernier puisse communiquer le sien au système. De plus, les SBC sont se prêtent principalement bien au diagnostic, à l’interprétation, alors que nos domaines cibles sont plutôt de type recherche opérationnelle, optimisation, planification. etc. Notre stratégie est différente, et ne s’appuiera pas sur le concept de SBC.

3. Approche proposée

Le but est donc d’accélérer la résolution (i.e. gagner en complexité), mais pour une instance donnée, c’est-à-dire particulariser la résolution. L’idée ici est donc qu’à la vue des connaissances qui se dégagent d’une instance donnée, un expert peut «spécialiser le programme». Ainsi, ici aussi l’expert va faire profiter le calculateur de ses connaissances supplémentaires, mais il n’y aura pas à priori de lien entre la résolution de deux instances différentes. De plus, concernant la complexité, il existe peu de support théorique permettant d’appuyer ces systèmes à base de SBC. En effet, les SBC peuvent devenir tellement complexes que donner des garanties de performance s’avère extrêmement difficile. Or dans notre approche, le support théorique d’une part (à savoir l’étude de certaines classes de complexité interactives) et la simplicité des objectifs (pas de modélisation de connaissances, juste un guidage du calculateur pour accélérer la résolution) d’autre part permettent beaucoup plus facilement ces garanties de performances.

Concernant la partie logicielle du projet, on pressent que, pour qu’un utilisateur extérieur puisse contrôler dynamiquement l’exécution d’un programme, des techniques telles le tissage pourront être utiles. Ces techniques sont déjà utilisées en algorithmique distribuée, (on l’on peut par exemple changer dynamiquement les spécifications des composants d’une application distribuée, cf projet Jacquard (INRIA) [?]), mais la motivation est dans ce cas d’appréhender la complexité d’une exécution distribuée, et non le gain en complexité algorithmique. D’un point de vue technique donc, le programme a donc été réalisé sans utiliser ces méthodes «dynamiques», et ce sans perte de généralité, comme nous le verrons au chapitre 6.

4. Justification du problème pratique choisi

L’idée ici est donc de «spécialiser le programme» à la vue des connaissances qui se dégagent d’une instance donnée. Pour pouvoir envisager un cas pratique, il nous a donc fallu trouver un problème pour lequel il n’y a pas besoin d’un «vrai» expert dans un domaine précis. Nous avons donc choisi le problème du puzzle, qui, bien qu’étant un problème «jouet», rentre parfaitement dans notre contexte et permet de dégager des idées générales :

– l’humain a bien ici les compétences d’un expert : étant donné une instance particulière de puzzle (i.e. des pièces en désordre), il est capable de dégager une connaissance supplémentaire, spécifique à cette instance (par exemple le sens de l’image) et ainsi inférer la solution et aider le calculateur à faire ses choix (i.e. où poser les pièces)

– cette situation reflète bien le cas général ou l’expert peut avoir une intuition sur :

• les bornes des valeurs de certaines variables du problème (i.e. par exemple dans notre cas, dire que telle pièce devra être placée dans telle région du puzzle)

• la corrélation de certaines variables (par exemple déclarer que deux pièces doivent être attachées, même si on ne sait pas où elles seront posées au final)

• l’invalidité de certaines solutions (par exemple voir qu’il est inutile de poser une pièce dans une

région donnée) L’implémentation du modèle proposé sera donc simplement adaptée à la résolution d’un puzzle, sans perte de généralité.

5. Présentation du document

La partie I du rapport sera consacrée à la théorie. Nous allons donner un aperçu des modèles théoriques (interactifs) existants. Après avoir donné les définitions générales nécessaires (en section 1.1.), nous aborderons en détail un premier modèle : PCP. Nous en étudierons d’abord en 1.2. certaines propriétés simples, pour ensuite examiner au 1.2..2 un théorème récemment re-démontré (cf [?]), ainsi que ses conséquences (en section ??). Les autres modèles et leur propriétés seront plus rapidement présentés au chapitre 2. Le chapitre 3 de cette partie théorique sera consacré à l’analyse de notre problème pratique.

La partie II vise à construire un modèle afin de définir ce qui signifie pour nous l’interaction entre un expert et un calculateur. Le chapitre 4 traitera du niveau le plus général, le chapitre 5 mettra l’accent sur les problèmes liés à la pratique, et l’implémentation réalisée ainsi que les résultats seront présentés au 6.

Première partie

Systèmes interactifs et théorie de la complexité Introduction de la partie théorique

Il existe de nombreux modèles théoriques pour modéliser l’interaction entre un calculateur (typiquement machine de Turing) et une entité type «oracle». En effet il y a plusieurs paramètres peuvent varier ([?]) : le calculateur peut être plus ou moins puissant et autorisé où non à utiliser de l’aléa, l’oracle peut être bienveillant ou malicieux, autorisé où non à voir ce que fait le calculateur, les questions peuvent être posées en une fois, ou sous forme de dialogue. Nous allons donc aborder trois modèles : les «probabilistically checkable proof» (PCP), qui sera étudié plus en détail, les protocoles «Arthur-Merlin» (AM), et enfin les «Interactive Proof» (IP). Nous essaierons au maximum de donner des liens entre ces modèles.

Chapitre 1

Étude d’un modèle d’interactivité : PCP

Afin de pouvoir expliciter en détail certaines propriétés des PCP, nous donnerons dans ce chapitre quelques définitions, afin de bien fixer les classes dont nous parlons.

1.1. Définitions

1.1..1 Rappels sur P et NP

Bien que P et NP soient des classes bien connues, il faut faire attention à bien préciser certains détails, en particulier ce qui ce qui ce passe dans les cas « négatifs ». Nous allons donc rappeler un certain nombre de définitions et de propriétés de base.

Pour les notations, t désignera ici une fonction de ℕ dans ℝ, n la longueur du mot en entrée, DT M (respectivement NDT M) signifiera machine de Turing déterministe (respectivement non déterministe).

Définition 1.1..1.1 On dit qu’une machine de Turing déterministe τ – accepte un langage L en temps t(n) ssi

w ∈ L ⟺ τ s’arrête sur l’entrée w en au plus t(n) transitions

– reconnaît un langage L en temps t(n) ssi (dans ce cas on distingue deux états d’arrêt, les acceptant et les rejetant)

w ∈ L ⟹ τ s’arrête dans un état acceptant sur l’entrée w en au plus t(n) transitions
w ∉ L ⟹ τ s’arrête dans un état rejetant sur l’entrée w en au plus t(n) transitions

Pour pouvoir adapter la définition pour le cas non déterministe, il faut préciser les conditions d’acceptation d’un mot :

Définition 1.1..1.2 Pour une NDTM τ, on dit :

– qu’une entrée w est acceptée ssi il existe une calcul de τ sur l’entrée w qui aboutit à un état acceptant – qu’une entrée w est acceptée en n transitions ssi w est acceptée et que n est la longueur du plus

petit calcul acceptant w

On peut alors donner des définitions concernant les langages :

Définition 1.1..1.3 On dit qu’une machine non déterministe τ – accepte un langage L en temps t(n) ssi :

w ∈ L ⟺ w est accepté en au plus t(n) transitions

Poursuivons donc avec deux ensembles de langages qui nous intéressent pour la suite :

Définition 1.1..1.4 Soit

– DTIME(t(n)) l’ensemble des langages reconnus par une machine de Turing déterministe en temps t(n)

– NTIME(t(n)) l’ensemble des langages acceptés par une machine de Turing non déterministe en temps t(n)

Enfin, rappelons la définition de deux classes bien connues :

Définition 1.1..1.5 Soit – P = ∪_{k≥1}DTIME(n^{k})

– NP = ∪_{k≥1}NTIME(n^{k})

Notons bien la petite dissymétrie dans ces deux définitions : pour un langage dans P, on a une machine (déterministe ) qui s’arrête tout le temps et qui peut nous dire si OUI ou NON le mot est dans le langage ; pour un langage dans NP, on a une machine (non déterministe) qui ne sait pas a priori répondre NON.

Nous pouvons à présent donner une première propriété bien connue qui relie P et NP (∥x, y∥ dénotant la concaténation des deux mots x et y).

Proposition 1.1..1.1 Un langage L est dans NP ssi il existe un langage L′ dans P et un entier n_{0} tels que :

x ∈ L ⇔ (∃y, y ≤ |x|^{n_{0}}) tq (∥x, y∥ ∈ L′))

Supposons L ∈ NP, alors ∃ NDTM τ_{1}, ∃k , tels que ∀x ∈ L, il existe au moins un calcul acceptant de τ_{1} de longueur inférieure à |x|^{k}. Notons r le degré d’indétermination de τ_{1}, et ajoutons r nouveaux symboles à l’alphabet. Pour tout x ∈ L, définissons donc un ensemble E_{x} de mots sur ces r nouveaux symboles : chaque mot y_{x} ∈ E_{x} représente un calcul acceptant de τ_{1} (avec x en entrée) de longueur inférieure à |x|^{k}. On sait que si x ∈ L, card(E_{x}) ≥ 1.

On pose donc n_{0} = k, et L′ = {∥x, y_{x}∥, x ∈ L, y_{x} ∈ E_{x}}. Par construction L′ et n_{0} vérifient bien l’équivalence annoncée. Reste à montrer que L′ est dans P. Considérons une machine τ_{2} qui, sur une entrée w .

– vérifie que que w est de la forme ∥x, y_{x}∥, avec y_{x} mot sur les r nouveaux symboles

– simule le calcul (sur l’entrée x) de τ_{1} qui correspond à y_{x} pour

– vérifier que y_{x} ∈ E_{x} (en effet même si on a vérifié que y_{x} est un mot sur le nouvel alphabet, il faut bien voir si les choix successifs indiqués sont bien faisables avec l’entrée x)

– vérifier que x ∈ L (si après avoir simulé le calcul on tombe sur un état acceptant, on déclare que

x ∈ L, sinon on déclare que x ∉ L) τ_{2} reconnaît bien le langage L′ (au sens de la définition 1.1..1.1), et le temps d’exécution est bien polynômial en la longueur de l’entrée. L′ est donc bien dans P.

Réciproquement, supposons qu’il existe un entier n_{0} et deux langages L et L′ vérifiant l’équivalence, et montrons que L ∈ NP. L′ ∈ P ⇒ ∃ DTM τ_{1} qui reconnaît L′ en temps polynômial en l’entrée x. Considérons une machine non déterministe τ_{2} qui, sur une entrée x :

– génère de manière non déterministe un mot y, |y| ≤ |x|^{n_{0}}

– simule la machine τ_{1} avec le mot ∥x, y∥ τ_{2} accepte bien L en temps polynômial en |x|. □

Remarque 1.1..1.1 Dans la fin de la démonstration précédente, τ_{2} fait même beaucoup mieux qu’accepter (au sens 1.1..1.3) L :

– cette machine ne boucle jamais

– pour les x dans L, il existe bien un calcul (de taille majorée par ) qui accepte x

– pour les x hors de L, on pourrait garantir que TOUS les calculs mènent vers un état rejetant ! Cependant, on peut montrer que ces conditions sont bien équivalentes à l’acceptation d’un langage pour une NDTM.

Remarque 1.1..1.2 (Une autre formulation) On peut aussi dire qu’un langage L est dans NP ssi il existe un vérificateur polynômial V et un entier n_{0} tels que :

– x ∈ L ⇒ ∃π_{x}, |π_{x}| ≤ |x|^{n_{0}}, V accepte (x, π_{x})

– x ∉ L ⇒ ∀π, |π| ≤ |x|^{n_{0}}, V rejète (x, π)

Cette dernière formulation prépare le terrain pour la définition de PCP, mais avant de pouvoir parler d’une machine PCP, il nous faut introduire les notions d’oracle et de machine randomisée.

1.1..2 L’oracle et l’aléa

L’oracle sera ici considéré comme un calculateur déterministe, infiniment puissant, pouvant donc répondre à tout problème décidable en O(1).

Définition 1.1..2.1 τ est une machine de Turing avec oracle si et seulement si τ est une machine de Turing habituelle, à laquelle s’ajoute :

– une bande de requête sur laquelle elle peut placer des mots de requête

– une bande de réponse sur laquelle l’oracle va écrire

– deux états q_{question} et q_{reponse}

Remarque 1.1..2.1 (Notation) Une machine avec oracle τ sera plutôt notée τ^{o}, le ^{o} indiquant que l’on peut la munir d’un oracle. Ainsi, si l’on utilise un oracle π pour répondre aux questions de cette machine τ, on notera la machine τ^{π}.

Pour ce qui est des machines de Turing probabilistes, nous donnerons le minimum servant à comprendre la suite, mais on pourra trouver des définitions plus détaillées dans [?].

Une machine de Turing aléatoire est munie d’une bande supplémentaire («bande d’aléa)» sur laquelle est inscrit, à chaque fois qu’une transition est franchie, un 1 ou un 0 (avec une probabilité \frac{1}{2}). La machine peut donc à tout moment lire le bit pointé sur cette bande d’aléa.

Ainsi, même si la machine est déterministe, on peut donc avoir plusieurs calculs différents pour une entrée donnée, selon le mot aléatoire r qui aura été tiré. Pour une machine aléatoire τ, on définit le temps de calcul sur l’entrée w par

– ∞ si la probabilité de terminer avec l’entrée w est strictement inférieure à 1

– la longueur du plus long calcul (terminant) sinon On va donc pouvoir maintenant définir une machine PCP, qui utilise à la fois une machine probabiliste et une machine à oracle.

1.1..3 Définition de PCP

Définition 1.1..3.1 (machine PCP) Une machine PCP τ (lisant un mot w) est composée en trois parties :

– une machine de Turing probabiliste τ_{1}, pouvant lire l’entrée w, qui génère un mot aléatoire r, puis en fonction de ce mot, m mots q_{1}, ⋯, q_{m} appelés mots de requête.

– une machine de Turing avec oracle τ_{2}^{o}, qui peut utiliser les mots de requête pour interroger un oracle. Ainsi elle disposera d’un mot y = b_{1}, ⋯, b_{m} constitués de m bits, un bit b_{i} étant la réponse de l’oracle à la requête q_{i}

– une machine de Turing déterministe τ_{3}, qui utilise w, r, et y pour accepter ou non l’entrée w.

On peut alors définir les classes de langages suivantes :

Définition 1.1..3.2 (P CP (r(n), q(n))) Soient r(n) et q(n) deux fonctions de ℕ dans ℚ^{+}.

On note P CP (r(n), q(n)) la classe des langages L tels qu’il existe une machine PCP τ dont le temps d’exécution est polynômial en |w| = n (au sens des machines probabilistes), qui utilise au plus O(r(n)) bits aléatoires, qui fait au plus O(q(n)) requêtes à l’oracle et telle que (les probabilités sont prises sur les mots aléatoires de τ_{1}) :

– Si w ∈ L, il existe un oracle π tel que P rob_{acc}^{τ_{π}} = 1

– Si w ∉ L, quel que soit l’oracle π, P rob_{acc}^{τ_{π}} < \frac{1}{2}

On va à présent faire quelques remarques pour éclaircir le fonctionnement de ces machines PCP.

Remarque 1.1..3.1 (Condition de rejet) Pour les mots hors du langage, on exige que P rob_{acc}^{τ^{π}} < \frac{1}{2}, ce qui est moins fort que P rob_{rej}^{τ^{π}} > \frac{1}{2}, car la machine peut aussi boucler.

Remarque 1.1..3.2 (Déterminisme de τ_{1}) Bien qu’étant probabiliste, τ_{1} reste déterministe : pour une entrée donnée w, pour chaque mot aléatoire r_{i}, on obtiendra toujours les mêmes requêtes q_{1} ⋯ q_{m}. Ces mots (qui dépendent aussi de w) seront donc parfois notés q_{r,1}...q_{r,m}. Comme le temps d’exécution de la machine PCP doit être polynômial, on sait que (avec |w| = n) ∃k tq la longueur de tous les q_{r,i} est majorée par n^{k}

Remarque 1.1..3.3 (Preuve détenue par l’oracle) On ne sait pas à priori comment fonctionne l’oracle. Cependant, comme celui ci est déterministe, on sait que :

Pour un mot fixé w, pour chaque question q_{r_{j},i}, l’oracle renvoie un bit π_{w,j,i}. Or, pour un L dans PCP(r(n),q(n)), le nombre de mots de requête possible est majoré par 2^{c_{1}r(n)}c_{2}q(n). On rappelle que pour chaque mot, l’oracle répond un bit. Ainsi, on peut considérer que pour chaque mot w, l’oracle est équivalent à une preuve (i.e. une chaîne sur {0, 1}^{∗})

π_{w} = (\begin{matrix}π_{w,0,0} & π_{w,0,1} & ⋯ & π_{w,0,c_{2}q(n)} \\ π_{w,1,0} & π_{w,1,1} & ⋯ & π_{w,1,c_{2}q(n)} \\ π_{w,2^{c_{1}r(n)},0} & π_{w,2^{c_{1}r(n)},1} & ⋯ & π_{w,2^{c_{1}r(n)},c_{2}q(n)} \end{matrix})

Quand on lui pose la question q_{r_{j},i}, l’oracle renvoie juste le bit (j,i) de π_{w}.

Remarque 1.1..3.4 (Notation) Si C_{1} et C_{2} sont deux classes de fonctions de ℕ dans ℚ^{+}, on note

P CP (C1, C2) = ∪_{r∈C_{1},q∈C_{2}}P CP (r(n), q(n))

1.2. Propriétés de PCP

1.2..1 Résultats immédiats

Ces premières propriétés simples sont surtout utiles pour mieux comprendre PCP.

Proposition 1.2..1.1 P = P CP (0, 0), et NP = P CP (log, poly) = P CP (0, poly)

L’égalité P = P CP (0, 0) vient du fait qu’une machine PCP τ = (τ_{1}, τ_{2}, τ_{3}) qui ne fait aucun tirage aléatoire et aucune requête à l’oracle se «réécrit» τ = τ_{3} (on rappelle que τ_{3} est une DTM dans la définition de PCP). Les conditions d’acceptation de P et de P CP sont alors équivalentes, car dans les deux définitions on doit accepter ou rejeter en un nombre polynômial de pas, et les probabilités des PCP sont réduites à 1 ou 0 puisqu’il n’y a ni aléa ni oracle.

Pour la deuxième partie de la proposition, montrons d’abord que P CP (log, poly) ⊆ NP.

Soit L ∈ P CP (log, poly), et τ^{o} une machine PCP reconnaissant L (τ^{o} étant composée de τ_{1}, τ_{2}, τ_{3}). ∃c_{1}, c_{2}, k, k′ tq ∀w ∈ L, |w| = n tq

– le nombre de tirages aléatoires faits par τ_{1} est majoré par a = c_{1}log(n)

– le nombre de mots de requête utilisés par τ_{2} est majoré par c_{2}n^{k}

– le temps d’exécution de la machine PCP est majoré par n^{k′} On va construire le vérificateur V suivant :

Routine vérificateur(w,π:mots binaires )

Variable

r:chaîne binaire { r va contenir tous les mots aléatoires possibles } y:chaîne binaire { y va contenir les bits répondus par l’oracle }

Début

Pour i variantDe 1 à 2^{a} Faire \{ \frac{2^{a}}{2} + 1 suffirait \}

r = i

       Simuler au plus n^{k′} transitions de la machine τ_{1}
       avec w en entrée et r comme mot aléatoire «imposé»
       Si Les mots de requêtes ont été calculés Alors
          Récupérer ces mots de requête q_{r_{1}} · · · q_{r_{m}}

Sinon

          REJETER

FinSi

y ← π(i, 1).π(i, 2). · · · .π(i, m)

       Simuler au plus n^{k′} transitions de la machine τ_{3}
       avec (w, r, y) en entrée
       Si τ_{3} rejète (w, r, y) OU le calcul n'est pas terminé Alors
          REJETER

FinSi FinPour

    ACCEPTER

Fin

Les conditions d’acceptation/refus décrite en 1.1..1.2 sont donc bien respectées. De plus le temps d’exécution est bien majoré par cst . 2^{a} . n^{k′} = cst . n^{c_{1}} . n^{k′}, ce qui est bien polynômial en la longueur de (w, π). Donc L ∈ NP.

Montrons que NP ⊆ P CP (0, poly). Soit L ∈ NP. D’après la proposition 1.1..1.1, page 7, on sait que ∃L′ ∈ P et un entier n tels que : x ∈ L ⇔ (∃y, y ≤ |x|^{n}) tq (∥x, y∥ ∈ L′)). Notons τ_{P} une machine de Turing décidant L’.

On construit la machine PCP τ = (τ_{1}, τ_{2}^{o}, τ_{3}) suivante (l’entrée est notée w) :

– τ_{1} ne fait pas de tirage aléatoire

– τ_{2} demande à l’oracle un mot y, |y| ≤ |w|^{k} (rappel : une requête par bit)

– τ_{3} = τ_{P} Si w ∈ L, on peut bien exhiber un oracle π tel que P rob_{acc}^{τ^{π}}(w) = 1 (On choisit par exemple l’oracle qui

simule τ_{P} et essaye en O(1) tous les y, |y| ≤ |w|^{n}). Si w ∉ L, on a même P rob_{acc}^{τ^{π}}(w) = 0. □

1.2..2 Démonstration d’un résultat analogue au théorème PCP

Le théorème PCP [?] dit que P CP (log, 1) = NP. On a déjà vu que P CP (log, poly) ⊂ NP, il est donc clair que P CP (log, 1) ⊂ NP. Cependant l’autre

inclusion est très puissante : avec un nombre constant de requêtes, on arrive à capturer NP.

Pour comprendre comment faire avec un nombre constant de requêtes, nous allons étudier une démonstration d’un résultat analogue, mais un peu moins puissant :

Théorème 1.2..2.1

NP ⊂ P CP (n^{3}, 1)

On va en fait démontrer que 3−SAT ∈ P CP (n^{3}, 1), ce qui est équivalent puisque 3-SAT est NP complet.

Notations

On considère donc n variables x_{i}, i ∈ ⟦1, n⟧. L’entrée du problème sera donc une formule sous forme 3CNF, ie ϕ = ⋀_{i=1}^{m} c_{i} avec, c_{i} = (l_{j_{i_{1}}} ∨l_{j_{i_{2}}} ∨l_{j_{i_{3}}} ),

avec j_{i_{p}} ∈ ⟦1, n⟧, pour p = 1, 2 ou 3, et l_{j_{ip}} = x_{j_{ip}} ou \overline{x_{j_{ip}}}.

ϕ est donc une formule avec m clauses et n variables, avec m = O(n^{3}). ϕ ∈ 3 − SAT ⟺ ∃a ∈ {0, 1}^{n}/ϕ(a) = 1.

Objectif

On veut construire une machine PCP τ, prenant en entrée une formule ϕ de la forme ci dessus, utilisant O(n^{3}) bits aléatoires et O(1) requêtes à l’oracle, et telle que :

a) si ϕ est satisfiable, il existe un oracle π tel que P rob_{acc}^{τ^{π}}(ϕ) = 1

b) si ϕ n’est satisfiable, quel que soit l’oracle π, P rob_{acc}^{τ^{π}}(ϕ) < \frac{1}{2}

Plan de la preuve

1) Pour se donner une première intuition, on va voir quelle machine PCP et quel oracle on peut exhiber pour (avec un nombre constant de requêtes à l’oracle)

– accepter ϕ à coup sur si ∃a ∈ {0, 1}^{n}/ϕ(a) = 1

– ne pas accepter ϕ avec une probabilité plus grande que \frac{1}{2} quand un oracle nous donne un a ∈

{0, 1}^{n}/ϕ(a) = 0

2) Cependant nous devrons modifier cette machine PCP, car quand ϕ n’est pas satisfiable, il faut rejeter avec une bonne probabilité quel que soit l’oracle, et pas seulement quand on oracle nous donne un a qui ne satisfait pas ϕ, autrement dit il faudra se protéger contre les oracles malicieux. Pour cela, nous allons construire le test de linéarité et le test de cohérence.

Partie 1)

On a donc en entrée un mot w. Il faut tout d’abord vérifier, (cela se fait bien en temps polynômial), que le mot w correspond bien à un formule ϕ sous forme annoncée.

La question à présent est donc ∃a ∈ {0, 1}^{n}/ϕ(a) = 1 ? On ne peut pas demander directement a à l’oracle, car cela coûterait n requêtes, il faut trouver un moyen qui utilise un nombre constant de requêtes.

Associons à ϕ = ⋀_{i=1}^{m}(l_{j_{i_{1}}} ∨ l_{j_{i_{2}}} ∨ l_{j_{i_{3}}} ) le polynôme, à coefficient sur Z_{2}, p = ∑_{i=1}^{m} p_{i} , avec p_{i} =

f(l_{j_{i_{1}}} ) . f(l_{j_{i_{2}}} ) . f(l_{j_{i_{3}}} ), et f(l_{j_{ip}}) = \{ \begin{matrix}1 − x_{j_{ip}} & si & l_{j_{ip}} = x_{j_{ip}} \\ x_{j_{ip}} & si & l_{j_{ip}} = \overline{x_{j_{ip}}} \end{matrix}

Remarquons que ∀a ∈ {0, 1}^{n}, c_{i}(a) = 1 ⟺ P_{i}(a) = 0. Le polynôme p donc a les propriétés suivantes (pour tout a) :

– ϕ(a) = 1 ⟹ p(a) = 0

– p(a) = 1 ⟺ le nombre de clauses de ϕ insatisfaites par a est impair Supposons que le vérificateur ait la valeur p(a).

– Si p(a) = 1 alors il sait que a ne satisfait pas ϕ

– Si p(a) = 0, il sait seulement qu’un nombre pair de clauses c_{i} sont insatisfaites, mais il voudrait savoir

si ce nombre est 0 Pour régler ce problème, le vérificateur va choisir aléatoirement un sous-ensemble de clauses sur lequel évaluer a. Il tire un mot aléatoire r ∈ {0, 1}^{m}, et calcule p^{r} = ∑_{i=1}^{m} r_{i}p_{i}. Ce polynôme p^{r} vérifie :

– ϕ(a) = 1 ⟹ p_{i}(a) = 0, ∀j ∈ ⟦1, m⟧ ⟹ p_{r}(a) = 0, ∀r ∈ {0, 1}^{m}

– ϕ(a) = 0 ⟹ ∃k tq c_{k}(a) = 0, et donc p_{k}(a) = 1. Quelle est alors la probabilité qu’on choisisse un r tel que pr(a) = 0 ? On a p^{r}(a) = ∑_{i≠k} r_{i}p_{i}(a) + r_{k}p_{k}(a) = ∑_{i≠k} r_{i}p_{i}(a) + r_{k}. Il y a donc une probabilité de \frac{1}{2} le r_{k} change la valeur dep^{r}(a). Donc si a ne satisfait pas ϕ, P r[p^{r}(a) = 0] = P r[p^{r} = 1] = \frac{1}{2}.

Si le vérificateur avait la valeur de p^{r}(a), il pourrait conclure que «ϕ est satisfiable ssi p^{r}(a) = 0», en respectant bien les propriétés d’acceptation exigées (cf «Objectifs» ).

Il nous faut donc construire une preuve qui permet au vérificateur de calculer p^{r}(a) sans lire toute la preuve et donc sans savoir précisément la valeur de a. On peut maintenant décrire un peu mieux la preuve qui sera vérifiée. La preuve π va encoder les valeurs de trois fonctions L_{1}^{a}, L_{2}^{a}, L_{3}^{a} :

L_{1}^{a} : {0, 1}^{n} ⟶ {0, 1}

(y_{1}, ..., y_{n}) ⟼ ∑_{1≤i≤n} a_{i}y_{i}

L_{2}^{a} : {0, 1}^{n^{2}} ⟶ {0, 1}

(y_{1,1}, ..., y_{n,n}) ⟼ ∑_{1≤i,j≤n} a_{i}a_{j}y_{i,j}

L_{3}^{a} : {0, 1}^{n^{3}} ⟶ {0, 1}

(y_{1,1,1}, ..., y_{n,n,n}) ⟼ ∑_{1≤i,j,k≤n} a_{i}a_{j}a_{k}y_{i,j,k}

Trois choses doivent être remarquées :

– ces fonctions sont linéaires

– on peut écrire entièrement les tables de valeur de ces trois fonctions en utilisant 2^{n} + 2^{n^{2}} + 2^{n^{3}} bits.

– si le vérificateur cherche à calculer L_{i}^{a} pour un point précis il peut le faire en consultant un seul point de cette liste de bits.

Pour se servir de cette preuve pour calculer p^{r}(a), il suffit donc de trouver les c_{i} tels que p^{r}(a) = L_{1}^{a}(c_{1}) + L_{2}^{a}(c_{2}) + L_{3}^{a}(c_{3}) (en développant l’expression p^{r}(a)), et d’envoyer ces 3 mots de requête à l’oracle (i.e. consulter les points c_{1}, c_{2} et c_{3} de la preuve π).

On a donc démontré le résultat partiel suivant :

Proposition 1.2..2.2 Si le vérificateur reçoit une formule ϕ et une preuve encodant les valeurs de L_{1}^{a}, L_{2}^{a} et L_{3}^{a} il peut choisir aléatoirement un r ∈ {0, 1}^{m} et calculer p^{r}(a) en lisant 3 bits de preuve. Si a satisfait ϕ alors le vérificateur constate que p^{r}(a) = 0 (et donc accepte le mot ϕ) peu importe son choix de r. Si a ne satisfait pas ϕ alors le vérificateur constate p^{r}(a) = 0 (et donc accepte le mot ϕ) avec probabilité \frac{1}{2}. En remarquant aussi que m = O(n^{3}) et donc que ce processus utilise au plus n^{3} bits aléatoires.

Il faut maintenant traiter le cas des oracles malicieux.

Partie 2)

Le plus dur reste à faire. On sait ce que devrait être la preuve si ϕ est satisfiable mais il faut construire des mécanismes qui permettent de rejeter avec forte probabilité n’importe quelle preuve lorsque ϕ est insatisfiable.

On peut supposer que toutes les preuves sont de longueur 2n + 2n^{2} + 2n^{3}. Notre vérificateur va faire passer une batterie de tests à la preuve potentielle. On veut construire ces tests de façon à ce qu’une preuve de la forme désirée passe tous ces tests avec probabilité 1.

Partie 2.1) Stratégie générale

Il va y avoir deux tests (linéarité et cohérence) à passer, pour ensuite calculer comme précédemment p^{r}(a) = L_{1}^{a}(c_{1}) + L_{2}^{a}(c_{2}) + L_{3}^{a}(c_{3}).

Informellement, la stratégie est la suivante :

• test de linéarité : refuser les preuves π représentant des fonctions trop «éloignées» de fonctions linéaires • ensuite, on pourra supposer que les fonctions qui ont réussi le test sont assez «proches» de fonctions

linéaires l_{i}, et se servir de cela pour ⋄ créer un évaluateur qui va, avec un c_{i} en entrée, retourner avec une bonne probabilité la valeur l_{i}(c_{i}) (bien sûr le terme «évaluateur» ne dénote pas une éventuelle machine supplémentaire par rapport à la machine τ que nous sommes en train de construire, tout cela se passera au sein du vérificateur) ⋄ le test de cohérence : refuser les preuves π représentant des fonctions linéaires l_{i} qui ne seraient pas

du type L_{1}^{a}, L_{2}^{a}, L_{3}^{a} ⋄ calculer pr(a) et accepter ssi on trouve 0

Partie 2.2) Présentation du test de linéarité et de l’évaluateur

Les preuves sont censées représenter trois fonctions linéaires. Donc si on choisit au hasard deux points y_{1}, y_{2} ∈ {0, 1}^{n_{i}}, on devrait avoir L_{i}^{a}(y_{1} ⊗ y_{2}) = L_{i}^{a}(y_{1}) + L_{i}^{a}(y_{2}).

– Bonne nouvelle : si la preuve représente effectivement des fonctions linéaires tous ces tests seront passés sans problème.

– Mauvaise nouvelle : si la preuve contient des fonctions qui sont presque linéaires alors la probabilité de

détecter un problème est excessivement faible. On va être obligé de “faire avec” des preuves qui représentent des fonctions quasi-linéaires, c’est à dire des fonctions qui diffèrent d’une fonction linéaire sur un tout petit nombre de points. Les fonctions qui ne sont pas quasi-linéaires vont échouer notre test avec une probabilité suffisamment forte. Les fonctions quasi-linéaires vont être suffisamment proches d’une fonction linéaire pour que l’on corrige les erreurs, avec l’évaluateur.

Partie 2.3) Le test de linéarité

Définition 1.2..2.1 (Une définition préliminaire) Soit p ∈ ℕ, f et g, {0, 1}^{p} ⟼ {0, 1}. On dit que f et g sont δ-proches ssi

P rob_{x∈{0,1}^{p}}[f(x) ≠ g(x)] ≤ δ

Voici maintenant le test de linéarité : pour tester si une fonction f, {0, 1}^{p} ⟼ {0, 1} est quasi-linéaire : on choisit aléatoirement x et y ∈ {0, 1}^{p}, on répond oui si et seulement si f(x ⊗ y) = f(x) + f(y).

Notez que dans notre cas, pour tester si l’on a bien trois fonctions linéaires l_{1}, l_{2}, l_{3} (on aura donc p = n, n^{2}, et n^{3}) on aura besoin de O(n^{3}) bits aléatoires et la lecture de trois bits de preuve.

Lemme 1.2..2.3 (Propriété du test de linéarité) Deux résultats :

1) (évident :) Si f est linéaire alors le test de linéarité est toujours un succès

2) ∀δ < \frac{1}{3}, f n’est pas δ-proche d’une fonction linéaire l alors P rob[test réussi] ≤ 1 − \frac{δ}{2}

△ Soit δ < \frac{1}{3}. Démontrons le second point par la contraposée.

On suppose donc que f, \{0, 1\}^{p} ⟼ \{0, 1\}, est telle que P rob_{x,y}[f(x ⊗ y) ≠ f(x) + f(y)] ≤ \frac{δ}{2}, et l’on veut montrer qu’il existe une fonction linéaire l, {0, 1}^{p} ⟼ {0, 1} qui est δ-proche de f.

Construisons une telle fonction l. Soit x ∈ {0, 1}^{p}. On veut définir l(x). Remarquons que comme f n’est pas forcement linéaire, E_{0} = {y ∈ {0, 1}^{p} tq f(x⊗y)−f(y) = 0} et E_{1} = {y ∈ {0, 1}^{p} tq f(x⊗y)−f(y) = 1} peuvent être non vides tous les deux. Définissons donc

l(x) = \{ \begin{matrix}0 & si & card(E_{0}) > card(E_{1}) \\ 1 & sinon \end{matrix}

Il faut à présent montrer

Lemme intermédiaire 1.2..2.4 Deux propriétés de l :

1) l est δ-proche de f

2) l est linéaire ⋆ Supposons que l n’est pas δ-proche de f, i.e. P rob_{x}[f(x) ≠ l(x)] > δ.

P rob_{x,y}[f(x ⊗ y) − f(y) ≠ f(x)] ≥ P rob_{x,y}[f(x ⊗ y) − f(y) = l(x) ∧ l(x) ≠ f(x)]
= P rob_{x}[l(x) ≠ f(x)] . P rob_{y}[f(x ⊗ y) − f(y) = l(x) ∧ l(x) ≠ f(x)]
+ P rob_{x}[l(x) = f(x)] . 0
= P rob_{x}[l(x) ≠ f(x)] . P rob_{y}[f(x ⊗ y) − f(y) = l(x) ∧ l(x) ≠ f(x)]
= \underbrace{P rob_{x}[l(x) ≠ f(x)]}_{> δ} . \underbrace{P rob_{y}[f(x ⊗ y) − f(y) = l(x)]}_{≥ \frac{1}{2} par construction de l}

Or par construction de l, on a ∀x, P rob_{y}[l(x) = f(x ⊗ y) − f(y)] ≥ \frac{1}{2}. On obtient P rob_{x,y}[f(x ⊗ y) − f(y) ≠ f(x)] > \frac{δ}{2}, ce qui est en contradiction avec l’hypothèse Donc l est δ-proche de f.⋆

Il faut aussi montrer que l est linéaire. ⋆ Considérons la probabilité p(x) = P rob_{y}[l(x) = f(x ⊗ y) − f(y)] Notre construction garantit p(x) ≥ \frac{1}{2},

mais en fait on va montrer que p(x) > 1 − δ. Notre hypothèse initiale sur f permet de dire que, ∀x :

P rob_{y,z}[(e1) f(x ⊗ y) + f(z) ≠ f((x ⊗ y) ⊗ z)] ≤ \frac{δ}{2}
P rob_{y,z}[(e2) f(x ⊗ z) + f(y) ≠ f((x ⊗ z) ⊗ y)] ≤ \frac{δ}{2}

Et donc

P rob_{y,z}[(e1) ∨ (e2)] ≤ δ
⟺ P rob_{y,z}[\overline{(e1)} ∧ \overline{(e2)}] ≥ 1 − δ
⟺ P rob_{y,z}[f(x ⊗ y) + f(z) = f(x ⊗ z) + f(y)] ≥ 1 − δ

Ce que l’on peut encore écrire P rob_{y,z}[f(x ⊗ y) − f(y) = f(x ⊗ z) − f(z)] ≥ 1 − δ.

On a donc

1 − δ ≤ P rob_{y,z}[f(x ⊗ y) − f(y) = f(x ⊗ z) − f(z)]
= ∑_{t∈{0,1}} P rob_{y,z}[(f(x ⊗ y) − f(y) = t) ∧ (f(x ⊗ z) − f(z) = t)]
= ∑_{t∈{0,1}} P rob_{y,z}[f(x ⊗ y) − f(y) = t] . P rob_{y,z}[f(x ⊗ z) − f(z) = t]
= ∑_{t∈{0,1}} P rob_{y}[f(x ⊗ y) − f(y) = t]^{2}

Or en remplaçant t par l(x) et 1 − l(x), et en constatant que

P rob_{y}[f(x ⊗ y) − f(y) = l(x)] = p(x)
et
P rob_{y}[f(x ⊗ y) − f(y) = 1 − l(x)] = 1 − p(x)

On obtient (en utilisant le fait que p(x) ≤ \frac{1}{2}) :

1 − δ ≤ p(x)^{2} + (1 − p(x))^{2} ≤ p(x)^{2} + p(x)(1 − p(x)) = p(x)

Pour résumer, on sait que

∀v, p(v) = P rob_{y}[l(v) = f(v ⊗ y) − f(y)] ≥ 1 − δ

En appliquant trois fois le résultat ci dessus, on a donc ∀x, x′

P rob_{y}[(e1) l(x) ≠ f(x ⊗ y) − f(x)] ≤ δ
P rob_{y}[(e2) l(x′) ≠ f(x′ ⊗ (x ⊗ y)) − f(x ⊗ y)] ≤ δ
P rob_{y}[(e3) l(x ⊗ x′) ≠ f((x ⊗ x′) ⊗ y) − f(y)] ≤ δ

Ainsi,

P rob_{y}[(e1) ∨ (e2) ∨ (e3)] ≤ 3δ ⟺ P rob_{y}[\overline{(e1)} ∧ \overline{(e2)} ∧ \overline{(e3)}] ≥ 1 − 3δ
⟹ P rob_{y}[l(x ⊗ x′) = l(x) + l(x′)] ≥ 1 − 3δ

Étant donné que δ < \frac{1}{3}, on a donc obtenu que

∀x, x′, P rob_{y}[l(x ⊗ x′) = l(x) + l(x′)] > 0

Si l n’était pas linéaire, on pourrait donc trouver au moins x_{0}, x0^{′} tels que l(x_{0} ⊗ x0^{′}) ≠ l(x_{0}) + l(x0^{′}), et donc tels que P rob_{y}[l(x_{0} ⊗ x0^{′}) = l(x_{0}) + l(x0^{′})] = 0, ce qui contredirait le résultat ci-dessus.

Donc l est linéaire. ⋆ (fin du lemme sur notre fonction l) △ (fin du lemme sur les propriété du test de linéarité)

Remarque 1.2..2.1 Grâce à la deuxième propriété du test de linéarité on va pouvoir, pour tout δ_{0} < \frac{1}{3} fixé, adapter le test pour garantir qu’une fonction non δ_{0} proche d’une fonction linéaire soit acceptée avec une probabilité inférieure à \frac{1}{2}. Il suffira en effet de répéter k fois le test, avec k vérifiant (1 − \frac{δ_{0}}{2} )^{k} < \frac{1}{2}.

Ainsi, pour les cas où ϕ n’est pas satisfiable :

– si l’oracle ne nous fournit pas une preuve représentant trois fonctions f_{i} toutes δ_{0}-proches de fonctions linéaires l_{i}, le contrat est rempli (i.e. probabilité d’accepter inférieure à \frac{1}{2})

– sinon, on va pouvoir garantir la probabilité d’acceptation inférieure à \frac{1}{2} grâce au test de cohérence, qui aura justement de bonnes propriétés puisque l’on pourra supposer que les fonctions à l’entrée de ce test sont δ_{0} proches de fonctions linéaires !

Partie 2.4) L’évaluateur

L’évaluateur de fonction va prendre en entrée un x ∈ {0, 1}^{n^{k}}, (k = 1, 2 ou 3) et, en consultant O(1) bits de la preuve qui représente 3 fonctions f_{i}, va retourner une valeur E(x) vérifiant

– Si f_{i} est linéaire alors E(x) = f_{i}(x)

– Si f_{i} est δ-proche d’une fonction linéaire l_{i}, P rob[E(x) = l_{i}(x)] ≥ 1 − 2δ Algorithme pour l’évaluateur (x est fixé) :

– choisir aléatoirement un y ∈ {0, 1}^{n^{k}}

– retourner E(x) = f_{i}(x ⊗ y) − f_{i}(y) Cela requiert la lecture de deux bits de la table de f_{i}. Il est clair aussi que si f_{i} est linéaire alors

E(x) = fi(x).

Si f_{i} est δ-proche d’une fonction linéaire l_{i} alors

P rob_{y}[(e1) f_{i}(y) ≠ l_{i}(y)] ≤ δ
P rob_{y}[(e2) f_{i}(x ⊗ y) ≠ l_{i}(x ⊗ y)] ≤ δ

Et donc

P rob_{y}[(e1) ∨ (e2)] ≤ 2δ
⟺ P rob_{y}[\overline{(e1)} ∧ \overline{(e2)}] ≥ 1 − 2δ
⟺ P rob_{y}[f_{i}(x ⊗ y) = l_{i}(x ⊗ y) ∧ f_{i}(y) = l_{i}(y)] ≥ 1 − 2δ
⟹ P rob_{y}[f_{i}(x ⊗ y) − f_{i}(y) = l_{i}(x ⊗ y) − l_{i}(y)] ≥ 1 − 2δ
⟺ P rob[E(x) = l_{i}(x)] ≥ 1 − 2δ

Partie 2.5) Le test de cohérence

Présentation : Le test de cohérence reçoit les tables de f_{1}, f_{2} et f_{3}, qui sont linéaires ou δ-proches de fonctions linéaires l_{1}, l_{2} et l_{3} (avec un delta qu’on a pu imposer, cf remarque 1.2..2.1) . Le test est effectué en lisant un nombre fixe de positions des tables. Pour δ fixé, ce test a les propriétés suivantes :

– Si f_{1}, f_{2} et f_{3} sont du type L_{1}^{a}, L_{2}^{a} et L_{3}^{a} pour un même a ∈ {0, 1}^{n} alors le test est passé avec une probabilité de 1

– Si il n’existe aucun a ∈ {0, 1}^{n} tel que l_{1}, l_{2} et l_{3} sont du type L_{1}^{a}, L_{2}^{a} et L_{3}^{a} alors le test détecte cela avec une probabilité constante η > 0

Le fait que η soit constante permet d’être sûr que l’on pourra ré-itérer le test de cohérence pour atteindre une probabilité d’acceptation des fonctions non cohérente inférieure à \frac{1}{2}.

Algorithme :

– choisir aléatoirement x, x′, et x′′ ∈ {0, 1}^{n}, et y ∈ {0, 1}^{n^{2}}

– définir (x ± x′){0, 1}^{n^{2}}par(x ± x′)_{i,j} = x_{i}xj^{′}

– définir (x′′ ± y){0, 1}^{n^{3}}par(x′′ ± y)_{i,j,k} = xi^{′′}y_{j,k}

– utiliser l’évaluateur de fonctions pour calculer l_{1}(x), l_{1}(x′), l_{1}(x′′), l_{2}(x ± x′), l_{2}(y) et l_{3}(x′′ ± y)

– retourner oui ssi (condition1) l_{1}(x)l_{1}(x′) = l_{2}(x ± x′) et (condition2) l_{1}(x′′)l_{2}(y) = l_{3}(x′′ ± y) Vérifions d’abord que le test de cohérence est positif lorsque les fonctions sont de la forme L_{1}^{a}, L_{2}^{a} et L_{3}^{a}.

Dans ce cas on a :

L_{1}^{a}(x)L_{1}^{a}(x′) = (∑_{i} a_{i}x_{i})(∑_{j} a_{j}xi^{′})
= ∑_{i,j} a_{i}a_{j}x_{i}xj^{′}
= L_{2}^{a}(x ± x′)

et

L_{1}^{a}(x′′)L_{2}^{a}(y) = (∑_{i} a_{i}xi^{′′})(∑_{j,k} a_{j}a_{k}y_{j,k})
= ∑_{i,j,k} a_{i}a_{j}a_{k}xi^{′′}y_{j,k}
= L_{3}^{a}(x′′ ± y)

A présent vérifions ce qui se passe si les f_{i} sont δ-proches de fonctions l_{i}. Examinons seulement la «condition1» signalée dans l’algorithme ci dessus, car le raisonnement est le même pour la «condition2». La fonction l_{1} est linéaire et elle peut donc être écrite comme l_{1}(x) = ∑_{i} a_{i}x_{i}. De même la fonction l_{2} est linéaire et peut être écrite comme l_{2}(y) = ∑_{i,j} b_{i,j}y_{i,j}. Ces deux fonctions sont cohérentes si et seulement si b_{i,j} = a_{i}a_{j} pour tout i,j. Regardons ce qui se passe il y a k coefficients différents, c’est à dire b_{i_{1},j_{1}} ≠ a_{i_{1}}a_{j_{1}}, ..., b_{i_{k},j_{k}} ≠ a_{i_{k}}a_{j_{k}}.

Notre «condition1» est la comparaison entre l_{1}(x)l_{1}(x′) = ∑_{i,j} a_{i}a_{j}x_{i}xj^{′} et l_{2}(x ± x′) = ∑_{i,j} b_{i,j}x_{i}xj^{′}.

∑_{i,j} a_{i}a_{j}x_{i}xj^{′} − ∑_{i,j} b_{i,j}x_{i}xj^{′} = 1

⟺ ∑_{i,j} x_{i}xj^{′}(a_{i}a_{j} − b_{i,j}) = 1

⟺ ∑_{p=1}^{k} x_{i_{p}}xj_{p}^{′}(a_{i_{p}}a_{j_{p}} − b_{i_{p},j_{p}}) = 1

⟺ ∑_{p=1}^{k} x_{i_{p}}xj_{p}^{′} = 1

Résumé : Quelle est alors la probabilité de rejeter des f_{i} si l’erreur est sur la condition1 ? On peut dire que

(evaluation de l_{1}(x) reussie)

∧

(evaluation de l_{1}(x′) reussie)

∧

(evaluation de l_{2}(x ± x′ reussie)

∧ (\overline{condition1})

⟹ rejet a cause de condition1

Or P rob(\overline{condition1}) = P rob_{x,x′} [∑_{p=1}^{k} x_{i_{p}}xj_{p}^{′} = 1] = P rob_{x,x′} [∑_{p=1}^{k} x_{i_{p}}xj_{p}^{′} = 0] = \frac{1}{2}.

Et P rob(evaluation reussie) ≥ 1 − 2δ = c_{δ}. (c étant constante car δ est constante). Donc P rob(rejet a cause de condition1|condition1 violee) ≥ c_{δ}^{3} ∗ \frac{1}{2} = c_{1}. On peut faire de même pour la «condition2». Résumé général : Quelle est alors la probabilité de rejeter des f_{i} qui ne sont pas cohérentes ?

P rob(rejet) = \underbrace{P rob(condition1 violee)}_{α_{1}} \underbrace{P rob(rejet a cause de condition1|condition1 violee)}_{c_{1}}
+ \underbrace{P rob(condition2 violee)}_{α_{2}} \underbrace{P rob(rejet a cause de condition2|condition2 violee)}_{c_{2}}
= α_{1}c_{1} + α_{2}c_{2}
= c

La probabilité d’acceptation est donc la constante 1 − c, et l’on peut calculer une constante λ telle que (1 − c)^{λ} < \frac{1}{2}. On pourra donc répéter λ fois le test de cohérence pour garantir les objectifs initiaux. □ (fin de la démonstration de 3 − SAT ∈ P CP (n^{3}, 1))

Remarque : Pour coller plus au formalisme d’une machine PCP, noter qu’on pourrait ré-écrire la preuve en tirant d’abord tous les bits aléatoires dont on a besoin, puis tous les mots de requête.

1.3. Le théorème PCP

1.3..1 Les résultats obtenus

Dans sa démonstration, [?], Irit Dinur démontre que

NP = P CP (log(n.polylog(n)), 1))

ce qui est donc plus puissant encore que le résultat que nous venons de démontrer. Pour tout langage L ∈ NP, on sait donc qu’il existe en particulier une constante c_{L} telle que le nombre de requêtes à l’oracle sera majoré par c_{L}.

Il existe un résultat [?] assez troublant qui nous dit que, pour tout ϵ > 0, moyennant une complétude de 1 − ϵ et une sûreté de \frac{1}{2} + ϵ, on peut se contenter de tester le XOR de seulement 3 bits de preuve ! La constante est donc universelle !

Il existe encore d’autres raffinements du théorème PCP, mais NP = P CP (log(n), 1)) reste l’information majeure, comme nous le verrons en 1.4..

1.3..2 Un peu d’histoire

A l’origine le théorème PCP a été formulé dans le cadre des preuves interactives, vérifiables avec un nombre constant d’appels ; et la démonstration était un peu dans le même esprit que celle vue en 1.2..2 (mais utilisant des polynômes plutôt que nos trois fonctions linéaires, voir [?]). La formulation dans la démonstration d’Irit Dinur touche aux problèmes d’approximabilité :

Le théorème PCP est équivalent à dire que le problème «Gap 3-SAT» est NP dur.

Le problème «Gap 3-SAT» étant (avec S̄AT (ϕ) dénotant la plus petite fraction de clauses non satisfiables de ϕ) de distinguer si S̄AT (ϕ) = 0 ou S̄AT (ϕ) > α avec un α > 0.

La nouvelle démonstration d’Irit dinur utilise donc, entre autre, un raisonnement courant dans le contexte de l’inapproximabilité : la «gap amplification». En effet, pour démontrer que «Gap 3-SAT» est NP dur, la preuve va construire une réduction de 3-SAT à GAP 3-SAT. Avant de continuer remarquons qu’il faut faire attention au mot réduction ici, car GAP-3-SAT n’est pas un problème de décision habituel, il faudrait donc donner quelques définitions supplémentaires (cf [?]). L’idée est que pour écrire une telle réduction, il faut, étant donné une instance ϕ, de 3-SAT, construire ϕ′ telle que

– si S̄AT (ϕ) = 0 (i.e. ϕ satisfiable), S̄AT (ϕ′) = 0

– si S̄AT (ϕ) ≥ \frac{1}{n} (i.e. ϕ non satisfiable), S̄AT (ϕ′) > α

On voit donc que pour le cas négatif, il faut augmenter la proportion des clauses qui ne sont pas satisfiables, d’où le terme «gap amplification».

1.4. Conséquences du théorème PCP sur l’inapproximabilité

Dans cette partie on supposera connues les classes PTAS (Polynômial Time Approximation Scheme), APX (Approximable)et NPO (NP Optimisation). On rappelle de plus que P T AS ⊆ AP X ⊆ NP O et que si P ≠ NP, on a même P T AS ⊂ AP X ⊂ NP O.

Nous allons donner un exemple de résultat d’inapproximabilité, et expliquer où intervient le théorème PCP dans la démonstration. Nous devons pour cela commencer par mentionner ce que l’on appelle la «technique du fossé» :

Définition 1.4..0.1 (pour un problème de maximisation) Soit Q ∈ NP O et K un problème NP complet. Une réduction avec fossé (a, b) de K vers Q est une transformation polynomiale f des instances de K vers les instances de Q telle que :

– x ∈ K ⟹ v_{opt}(f(x)) ≥ b

– x ∉ K ⟹ v_{opt}(f(x)) ≤ a

On peut à présent énoncer le théorème suivant (qui pourrait être démontré facilement) :

Théorème 1.4..0.1 Soit Q ∈ NP O. Si il existe une réduction avec fossé (a, b) d’un problème NP complet K vers Q alors

Si P ≠ NP, il n’existe pas un algorithme d’approximation pour Q avec un ratio meilleur que \frac{b}{a}.

Le théorème PCP va en fait permettre de construire facilement de tels fossés. Considérons par exemple le problème de maximisation MAX − 3 − SAT ∈ NP O. Ce problème est dans AP X, on connaît d’ailleurs un algorithme de ratio \frac{8}{7}. Le théorème PCP va permettre la construction d’une réduction de fossé (1, 1 − δ), (avec δ = \frac{1}{8}), entre 3 − SAT et MAX − 3 − SAT et ainsi montrer qu’on ne peut pas trouver un meilleur ratio pour un algorithme polynômial.

Notons bien que même sans le théorème PCP on savait que P ≠ NP ⟹ P T AS ⊂ AP X, mais le théorème PCP nous a donc plutôt permis de classer certains problèmes.

D’autres modèles de preuve interactive

Lorsque l’on imagine un système interactif dans la pratique, on peut penser à un « dialogue » entre les deux parties. Or pour le moment, dans notre modèle PCP, toutes les questions sont posées « en une fois ». Il serait donc rassurant d’envisager un modèle dans lequel les questions successives vont dépendre des réponses que l’on a déjà obtenues. Nous présenterons donc dans ce chapitre, de manière informelle, deux modèles qui se rapprochent plus de cette notion de dialogue. Pour plus de détails concernant les définitions et propriétés de ce chapitre, on pourra consulter [?].

2.1. Les protocoles d’Arthur et Merlin

2.1..1 Définitions

Ici Arthur (un calculateur) et Merlin (l’oracle) vont discuter pour savoir si une entrée x est dans un langage L. Le dialogue va comporter un certain nombre de tours, chaque tour étant une question de Arthur ou une réponse de Merlin. Plus précisément,

– lors d’un tour de Arthur, ce dernier calcule sa question q (en temps polynômial en la longueur de |x|) en fonction d’un mot aléatoire r (tiré à chaque tour), et de toute «l’historique» de la discussion (i.e. il peut utiliser ses anciennes questions, ses anciens tirages aléatoires, les anciennes réponses de Merlin)

– lors d’un tour de Merlin, ce dernier , ayant à sa disposition la question courante q, ainsi que TOUTE l’historique de la discussion (il voit donc en particulier les mots aléatoires successifs que Arthur a tirés), donne une réponse y (de taille polynomiale en x)

Grâce à cette notion de tours, on va pouvoir définir des protocoles de dialogue :

Définition 2.1..1.1 A un mot prot ∈ (AM)^{∗} et un langage D ∈ P, on peut associer

a) un protocole de dialogue : on lit le mot prot en faisant à chaque lettre A lue un tour d’Arthur, et à chaque lettre M lue un tour de Merlin. Puis, lorsque la discussion est terminée (notons h l’historique de toute la discussion), Arthur accepte l’entrée x si et seulement si h ∈ D.

b) la classe prot des langages L que l’on peut décider en utilisant le protocole de dialogue prot (décider signifiant que pour tous les mots appartenant au langage, on doit avoir une fonction de Merlin qui nous permet d’accepter avec une bonne probabilité, et pour tous les mots hors du langage, on doit rejeter avec une bonne probabilité, quelle que soit la fonction de Merlin)

Remarque 2.1..1.1 Dans notre «définition» ci dessus, pour une classe prot donnée, le nombre de tour est fixé, alors qu’une définition plus complète permettrait que le nombre de tours dépende de la taille de l’entrée x. Cependant, cela ne sera pas gênant pour nous car les propriétés que nous allons présenter ne concernent que ces classes de langages dont le protocole est un mot fixé prot ∈ (AM)^{∗}.

2.1..2 Propriétés simples des classes Arthur-Merlin

Nous pouvons énoncer quelques résultats permettant de se faire une meilleure idée sur la puissance des classes Arthur-Merlin :

Proposition 2.1..2.1 A = BP P, M = NP, wAAAw′ = wAw′ , wMMw′ = wMw′

Les deux premières égalités nous donnent donc des liens avec d’autres classes connues : si l’on ne fait qu’un seul tour d’Arthur, cela revient à lire l’entrée, utiliser un mot aléatoire, et répondre des deux cotés avec une faible probabilité d’erreur, on retrouve donc la classe Atlantic City, et si l’on ne fait qu’un seul tour de Merlin, cela correspond à l’envoi d’un certificat de taille polynômial en la taille du mot x «discuté», on retrouvera donc la classe NP. Les deux autres résultats montrent que l’on peut se restreindre aux jeux entre Arthur et Merlin où chacun joue en alternance.

Ces premiers résultats découlent en fait directement des définitions des classes Arthur-Merlin. Nous allons présenter dans la section suivante des théorèmes beaucoup plus puissants.

2.1..3 Des résultats plus forts

Étant donné qu’Arthur envoie son mot aléatoire à Merlin, on pourrait imaginer que ce soit Merlin qui calcule la question. Ainsi, le seul rôle d’Arthur serait de vérifier à la fin que l’historique de la discussion h appartient à un langage donné D. Arthur est alors dit paresseux, et l’on peut redéfinir exactement comme en 2.1..1.1 les classes de langages (notées alors prot_{lazy} associées aux mots prot ∈ (AM)^{∗}. Le premier résultat est que cela ne change absolument rien ! On a donc,

Proposition 2.1..3.1 Pour tout mot prot ∈ (AM)^{∗}, prot_{lazy}=prot

D’autre part, il a été démontré que l’on ne gagne pas en puissance avec un grand nombre d’interactions, du moment que le nombre d’interactions reste constant (ce qui de toute façon est supposé ici, de par notre définition «réduite», cf remarque 2.1..1.1).

Théorème 2.1..3.2 Pour tout mot prot ∈ (AM)^{∗}, prot ⊆ AM.

On peut donc dire que dès que le mot prot contenant AM, prot = AM.

Enfin, concernant les conditions exigées lorsqu’un mot x doit être accepté, on peut montrer que si l’on impose que les mots appartenant au le langage soit acceptés avec une probabilité de 1, on obtient toujours les mêmes classes.

2.2. IP

On a vu dans la section précédente qu’Arthur pouvait être paresseux sans que cela ne change rien. Or le fait que Merlin puisse lui même calculer les questions vient principalement du fait qu’Arthur divulgue ses bits aléatoires à Merlin. On va donc considérer une variante des jeux d’Arthur-Merlin dans laquelle Arthur garde secret ses tirages aléatoires, c’est ce que l’on appelle les preuves interactives.

La définition est donc la même qu’en 2.1..1, si ce n’est que Merlin ne voit pas l’aléa utilisé par Arthur.

2.3. Liens entre ces classes

Pour éviter toute confusion, pour tout mot prot ∈ (AM)^{∗}, on notera prot_{AM} la classe de langage associée au sens des protocoles d’Arthur Merlin, et prot_{IP} la classe de langage associée au sens des protocoles de preuves interactives. On peut maintenant énoncer la propriété suivante :

Proposition 2.3..0.3 Pour tout mot prot ∈ (AM)^{∗}, prot_{AM}⊆prot_{IP} On notera que ce résultat est en fait également vrai pour les protocoles dont le nombre de tours dépend de l’entrée. Le principe de la démonstration est simple : pour reconnaître un langage avec un protocole dans lequel les bits aléatoires ne doivent pas être dévoilés, il suffit d’inclure ces bits aléatoires dans les questions posées !

Le théorème suivant, beaucoup moins évident, nous renseigne sur l’inclusion inverse (on notant (AM)^{k} =

\underbrace{AMAM..AM}_{k fois})

Théorème 2.3..0.4 Pour tout k ≥ 1, (AM)_{IP}^{k} ⊆ (AM)_{AM}^{(k+1)} = AM

On voit donc qu’il faut faire un «échange» de plus dans le protocole d’Arthur-Merlin pour capturer la classe (AM)_{IP}^{k}. La conséquence de ce théorème est que pour tout k ≥ 1, (AM)_{IP}^{k} = (AM)_{AM}.

Nous allons à présent voir un exemple d’utilisation de ces preuves interactives à travers un exemple «célèbre».

2.4. Le problème des graphes non-isomorphes

Rappelons avant tout le problème des graphes non isomorphes (GNI) :

– entrée : deux graphes non orientés G_{0} = (V_{0}, E_{0}) et G_{1} = (V_{1}, E_{1})

– sortie : Oui ssi G_{0} et G_{1} ne sont pas isomorphes, i.e. qu’il n’existe pas une permutation π des points

de V_{0} telle que (u, v) ∈ E_{0} ⟺ (π(u), π(v)) ∈ E_{1} Ce problème est intéressant car on ne sais pas si (GNI) ∈ NP. On va montrer que GNI ∈ (AM)_{IP}^{1} .

□ Arthur reçoit les deux graphes. Il choisit aléatoirement un i ∈ {0, 1} et une permutation π de V_{i}. Il envoie alors à Merlin le graphe H = π(G_{i}). Merlin retourne un j ∈ {0, 1}, censé être le numéro du graphe dont provient H. Arthur accepte la paire (G_{0}, G_{1}) (et donc conclut que les deux graphes ne sont pas isomorphes) ssi i = j. □

On remarque que l’on a bien une probabilité de 1 du côté acceptant (i.e. si (G_{0}, G_{1}) appartient à l’ensemble des couples de graphes non isomorphes, on a bien une fonction de Merlin qui peut toujours trouver si l’on a envoyé G_{0} ou G_{1}), mais que la probabilité de rejeter une entrée qui doit l’être n’est que de \frac{1}{2} (si les deux graphes sont isomorphes, Merlin ne peut pas savoir d’où provient H, il a donc une chance sur deux de donner la bonne réponse par hasard). Ce détail peut être réglé en répétant l’expérience : toujours avec deux graphes en entrée, si Arthur tire k bits aléatoires, k permutations et envoie k graphes à Merlin, la probabilité de bonne réponse est bien en \frac{1}{2^{k}}. Notons au passage que cette technique de répétition cache quelques difficultés ; même si elle s’applique bien ici, elle ne fonctionne pas dans le cas général.

Remarquons également que cette démonstration est simple car Merlin n’a pas accès aux bits aléatoires d’Arthur. Il existe en fait un résultat plus fort, disant que GNI ∈ (AM)_{AM}^{1}, mais la démonstration est beaucoup plus délicate (cf [?]).

Le problème du puzzle

On va s’intéresser à un problème dont la résolution peut être accélérée grâce à l’intéractivité :le puzzle. Nous avons déjà vu (en section 4.) que ce problème est un bon exemple en pratique : l’oracle peut facilement inférer une connaissance spécifique à l’instance. Il faudrait à présent formaliser ce problème pour en examiner l’intérêt théorique, et démontrer à quel point l’intéractivité est utile.

3.1. Définition formelle du problème d’optimisation combinatoire associé

Définition 3.1..0.1 Un puzzle P est défini par :

– Ses dimensions, i.e. (L_{P} , H_{P}) ∈ (ℕ^{∗})^{2}

– Les pièces disponibles, chacune munie de 4 connections (haut, bas, gauche, droite) : P ieces_{P} = {p_{i} = {(p_{i}(haut), p_{i}(bas), p_{i}(gauche), p_{i}(droite))} ∈ ℕ^{4}, i ∈ ⟦1, L_{P} ∗ H_{P} ⟧}

Remarque 3.1..0.1 (Taille de l’instance) On va considérer que la taille d’une puzzle P est son nombre de pièces.

Spécifions maintenant que signifie poser des pièces sur un puzzle.

Définition 3.1..0.2 (Disposition) On appelle disposition d’un puzzle P tout fonction partielle injective

D : L_{P} ∗ H_{P} ⟶ P ieces_{P}
(l, h) ⟼ p_{i}

On veut aussi exprimer le fait que deux pièces ne peuvent être posées côtes à côtes que si elles ont la même connection en commun.

Définition 3.1..0.3 (Voisines invalides) On dit que deux pièces p_{x_{1}}, p_{x_{2}} sont des voisines invalides dans la disposition D d’un puzzle P ssi ∃l_{1}, l_{2}, h_{1}, h_{2} tels que :

p_{x_{1}} = D(l_{1}, h_{1}) p_{x_{2}} = D(l_{2}, h_{2})

(l1 = l2 et h1 = h2 − 1 et p_{x_{1}}(bas) ≠ p_{x_{2}}(haut)

ou

l1 = l2 et h1 = h2 + 1 et p_{x_{1}}(haut) ≠ p_{x_{2}}(bas)

ou

h1 = h2 et l1 = l2 − 1 et p_{x_{1}}(droite) ≠ p_{x_{2}}(gauche) ou

h1 = h2 et l1 = l2 + 1 et p_{x_{1}}(gauche) ≠ p_{x_{2}}(droite))

Fig. 3.1 – Un exemple de puzzle et de disposition

Définition 3.1..0.4 (Disposition valide) On dit qu’une disposition D d’un puzzle P est valide ssi il n’existe pas deux pièces invalides dans D.

Définition 3.1..0.5 (Disposition complète) On dit qu’une disposition D d’un puzzle P est complète ssi la fonction D est totale.

Définition 3.1..0.6 Le problème de décision du puzzle est le suivant :

– entrée : Un puzzle P

– sortie : Oui ssi il existe une disposition complète et valide de P

3.2. Puzzle est compliqué (3-partition se réduit à puzzle)

Nous montrons ici que le problème Puzzle est NP complet, en construisant une réduction entre 3-partition, qui est NP complet au sens fort, et Puzzle.

Tout d’abord il est clair que Puzzle est dans NP, car on peut bien vérifier qu’une disposition est complète et valide en temps polynômial en la taille du puzzle. Avant d’écrire la réduction annoncée, rappelons le problème 3-partition :

– entrée : A = \{a_{i} ∈ ℕ^{∗}, i ∈ ⟦1, 3n⟧\} tq ∑_{i=1}^{i=n} a_{i} = nB et ∀i, \frac{B}{4} < a_{i} < \frac{B}{2}

– sortie : Oui ssi il existe une partition de A en n classes de même poids Étant donnée une instance I de 3-partition, construisons le puzzle P_{I} suivant (cf exemple 3.2) :

1. L_{P_{I}} = B, et H_{P_{I}} = n

2. construisons maintenant les pièces, pour i = 1 ⋯ n : – si a_{i} = 1, on construit p_{i} = (0, 0, 0, 0)

– si a_{i} = k, k ≤ 2, on construit p_{i_{1}} = (0, 0, 0, i), p_{i_{2}} = (0, 0, i, i) , ⋯, p_{i_{k_{1}}} = (0, 0, i, i), p_{i_{k}} = (0, 0, i, 0)

Fig. 3.2 – Un exemple de réduction

Comme 3-partition est un problème (numérique) NP complet au sens fort, on sait qu’il existe un polynôme p tel que le problème 3 − partition_{p} (i.e. lorsque l’on ne garde que les instances I_{p} de 3-partition dont la valeur du plus grand entier a_{i} est inférieure à un polynôme de la longueur de cette instance I_{p} codée en binaire) est NP complet. Pour ces instances I_{p}, la réduction proposée est donc bien polynomiale en la taille de l’entrée. De plus, on a bien :

I admet une 3-partition ⟺ P_{I} admet une disposition valide

3.3. Utilité de l’intéractivité pour Puzzle

Rappelons que nous avons choisi le problème du Puzzle pour essayer d’en trouver une résolution interactive en pratique. En effet nous avions remarqué que sur chaque instance donnée, l’oracle (humain) peut inférer des connaissances (par exemple le sens de l’image) qui auraient été très difficiles à inculquer de façon générale au calculateur. On devine qu’effectivement pour la résolution du problème Puzzle, l’oracle va être utile. Cependant on aimerait bien, grâce à la théorie, s’assurer que Puzzle peut bien se résoudre avec un petit nombre de requêtes à l’oracle.

Or, ce résultat est assuré puisque

(P uzzle ∈ NP ∧ NP = P CP (log(n), 1)) ⟹ P uzzle ∈ P CP (log(n), 1)

Deuxième partie

Un framework général pour l’intéractivité et une implémentation Comment concevoir l’intéractivité

4.1. Introduction

Notre but est donc d’interagir avec un calculateur pour le guider dans son exploration. Encore faudrait-il définir ce que l’on entend par « interagir ». Ainsi avant de discuter un modèle pour l’interaction, nous allons préciser le cadre dans lequel notre modèle à un sens.

Pour pouvoir interagir, on veut donc pouvoir contrôler l’état du calculateur et agir sur cet état. Les premières questions qui se posent sont donc :

1) Que signifie «l’état» du calculateur ?

2) Que signifie modifier «l’état» du calculateur ?

3) Comment l’oracle peut il agir : quels pouvoirs accorder à l’oracle ?

4) Comment prendre en compte les actions de l’oracle : quand l’oracle a-t-il le droit d’effectuer un changement ? Comment et quand prendre en compte ce changement ?

4.2. Les objectifs

Tout d’abord, on veut garantir une certaine réactivité. En effet si les choix de l’oracle sont pris en compte très longtemps après leur formulation, l’interaction n’est pas satisfaisante.

D’autre part, on voudrait que le surcoût lié à l’interaction soit raisonnable. En particulier quand l’oracle n’interagit pas, il faudrait que le calculateur puisse rester efficace.

Enfin, il faut à la fois l’oracle est le maximum de pouvoir possible, et que l’on puisse se protéger des oracles malicieux avec une bonne probabilité.

4.3. Les types de problèmes que l’on veut résoudre interactivement

A va donc a priori considérer n’importe quel problème de décision ou d’optimisation combinatoire, i.e. tous les problèmes du type :

– entrée : un ensemble de variables x_{i}, ayant chacune un domaine d_{i} un ensemble de contraintes C, (et éventuellement une fonction f à optimiser)

– sortie : une valeur v_{i} pour chaque x_{i}, respectant les contraintes C, (et éventuellement optimisant la fonction f)

4.4. Modèle

Nous pouvons à présent commencer à définir plus précisément le contexte qui nous intéresse, et ainsi répondre aux premières questions en définissant ce qu’est l’état du calculateur, ce que signifie agir sur cet état.

On a donc un calculateur (au sens générique) qui résout une instance d’un problème de d’optimisation ou de décision.

4.4..1 Une difficulté pour définir l’état

A tout instant t, le calculateur dispose de son ensemble concret C_{t} de solutions partielles (appelées "nœud") restant à explorer. Il peut demander un nœud à traiter, i.e. extraire, ou insérer un nœud via un insérer.

Il serait donc tentant de définir l’état du calculateur à un instant t comme étant

E_{t} = ensemble des nœuds de C_{t}

Or cela pose un problème. La correspondance entre l’ensemble «concret» manipulé par le calculateur et un ensemble au sens mathématique peut cacher un détail, comme nous allons le voir dans l’exemple suivant. Imaginons par exemple que C_{t} soit une FILE, et que l’extraction et l’insertion respectent donc le FIFO. Si à l’instant t la file est dans l’état C_{t} = [|x1, x2, x3|] l’ensemble E_{t}, et donc l’état du calculateur, serait {x1, x2, x3}. Or si la file avait été dans l’état C′_{t}[|x3, x2, x1|], l’ensemble E′_{t} aurait été le même, alors que ces deux situations ne sont bien sur pas similaires ! Par contre, si le calculateur disposait d’un ensemble C_{t}, et que l’extraction choisissait l’élément x ∈ C_{t} optimisant un critère fixé, la correspondance avec un ensemble «mathématique» serait correcte.

Revenons au cas général dans lequel C_{t}, l’extraction et l’insertion peuvent être quelconques. Ainsi pour pouvoir définir, dans notre modèle, ce que signifie «l’état» et «agir sur l’état» il faudrait distinguer deux cas :

a) Pour les extraction qui ne dépendent que des nœuds de C_{t} :

– Définir l’état à l’instant t comme étant E_{t} est correct

– Dans ce cas dire que l’oracle agit sur l’état veut donc dire que l’oracle transforme E_{t} en un E′_{t} = f_{oracle}(E_{t}).

– Pour que l’oracle puisse influencer le calculateur, il faudra qu’il connaisse ce que l’on appelle la politique de l’extraction. La politique étant la connaissance, pour tout couple d’éléments e_{i}, e_{j} dans E_{t}, de P rob_{E_{t}}(e_{i} choisi par extraire) ≥ P rob_{E_{t}}(e_{j} choisi par extraire). En effet si l’oracle n’avait aucune idée de quels éléments sont privilégiés par l’extraction, il ne pourrait pas influencer le calculateur

b) Pour les extraction qui ne dépendent pas que des nœuds de C_{t}, on a donc deux problèmes :

– On pourrait en effet avoir P rob_{E_{t}}(e_{i} choisi par extraire) > P rob_{E_{t}}(e_{j} choisi par extraire) et P rob_{E_{t′}} (e_{i} choisi par extraire) < P rob_{E_{t′}} (e_{j} choisi par extraire), avec E_{t} = E_{t′} ! On ne peut donc pas définir la politique de la même manière.

– De plus, étant donné que l’on sait que deux ensembles mathématiques égaux peuvent en fait représenter deux situations différentes pour le calculateur, on aimerait avoir un contrôle plus fin que simplement pouvoir enlever ou ajouter un élément à E_{t}.

Pour définir l’état du calculateur, on a donc toujours besoin de préciser E_{t}, mais on va rajouter une information : on supposera que

– ∃ ordre total <_{E_{t}} vérifiant la condition (ψ) suivante :

∀a, b ∈ E_{t}, a <_{E_{t}} b ⟹ prob(a choisi par extract dans C_{t}) ≤ prob(b choisi pas extract dans C_{t})

– Dans ce cas dire que l’oracle agit sur l’état veut donc dire que l’oracle transforme un état (E_{t}, <_{E_{t}}) en un (E′_{t}, <_{E′_{t}}) = f_{oracle}(E_{t}, <_{E_{t}})

– La politique étant cette fois ci la connaissance, pour tout couple d’éléments e_{i}, e_{j} dans (E_{t}, <_{E_{t}}), de

P rob_{(E_{t},<_{E_{t}})}(e_{i} choisi par extraire) ≥ P rob_{(E_{t},<_{E_{t}})}(e_{j} choisi par extraire). Dans ce dernier cas, il peut donc soit changer l’ensemble, soit «réorganiser les éléments».

4.4..2 Définition du modèle

Pour unifier la définition de l’état d’un calculateur et de l’action sur cet état, on va donc choisir l’approche b) :

1. L’état du calculateur est le couple (E_{t}, <_{E_{t}}), l’ordre vérifiant la condition (ψ)

2. On appelle un pas de calcul l’insertion ou l’extraction d’un nœud à traiter

3. Entre deux pas de calculs (E_{t}, <_{E_{t}}) ne change pas, au pas numéro i on a donc un ensemble (E_{i}, <_{E_{i}}) de solutions partielles

4. L’extraction ou l’insertion font donc passer d’un état (E_{i}, <_{E_{i}}) à un état (E_{i+1}, <_{E_{i+1}})

5. Le fait que l’oracle doive connaître la politique d’extraction de l’extraction se traduit simplement par le fait que l’oracle doit connaître les <_{E_{i}}

6. Agir sur l’état signifie calculer (E′_{t}, <_{E′_{t}}) = f_{oracle}(E_{t}, <_{E_{t}})

Remarquons que si l’extraction est en fait du type a), cela ne pose pas de problème, on peut bien définir la aussi un ordre total vérifiant (ψ). Par contre dans ce cas, quand l’oracle agit sur un état (E_{t}, <_{E_{t}}), il ne pourra pas changer <_{E_{t}}.

7. extraire doit vérifier (avec E_{i} ≠ ∅, et e l’élément fournit par extraire)

(E_{i}, <_{E_{i}}) ⟶^{extraire} (E_{i+1}, <_{E_{i+1}}) ⟹ \{ \begin{matrix}E_{i+1} ∪ \{e\} & = & E_{i} \\ <_{E_{i+1}} & = & <_{E_{i}|E_{i+1}} \end{matrix}

8. insérer doit vérifier (avec e l’élément que l’on insère)

(E_{i}, <_{E_{i}}) ⟶^{insert} (E_{i+1}, <_{E_{i+1}}) ⟹ \{ \begin{matrix}E_{i+1} & = & E_{i} ∪ \{e\} \\ <_{E_{i+1}|E_{i}} & = & <_{E_{i}} \\ <_{E_{i+1}} & est & total \end{matrix}

4.4..3 Exemples

Si C_{t}, extraire et insérer implémentent une pile, nous sommes dans le cas b). E_{i} est donc l’ensemble des éléments dans la pile après i pas de calculs. <_{E_{i}} est donc ici a ∈ E_{i} <_{E_{i}} b ∈ E_{i} ssi a à été inséré avant b dans la pile. Modifier E_{i} signifie donc enlever ou rajouter des éléments dans la pile, et changer <_{E_{i}} signifie donc permuter des éléments de la pile.

Si C_{t}, extraire et insérer représentent une file de priorité qui donne un élément x ∈ C_{t} tel que critère(x) est maximum. E_{i} est donc l’ensemble des éléments de la file après i pas de calculs. <_{E_{i}} est donc ici a ∈ E_{i} <_{E_{i}} b ∈ E_{i} ssi critère(a) ≤ critère(b). L’oracle peut ici modifier E_{i}, mais il ne peut pas modifier <_{E_{i}} car il faudrait qu’il modifier les éléments !

Si C_{t}, extraire et insérer représentent un ensemble tel que tous les éléments sont équivalents, i.e. l’extraction choisit indépendamment à chaque tour un élément selon une loi uniforme. E_{i} est donc l’ensemble des éléments de C_{t} après i pas de calculs. On peut choisir un <_{E_{i}} quelconque ! (puisque la probabilité de choisir un élément est la même pour tous les éléments !) L’oracle peut ici modifier E_{i}, ainsi que <_{E_{i}}, même si la modification de l’ordre n’a ici aucun effet.

Spécification d’un modèle pratique ou Vers la pratique

Le modèle spécifié en 4.4..2 définit donc les termes «état» et «agir» de manière générale. Cependant, on veut à présent s’interroger sur les contraintes que la pratique va imposer. Étant donné qu’il existe de nombreuses manières concrètes de représenter un «état» ou une «action», nous n’allons pas en détailler une en particulier. L’objectif de ce chapitre n’est pas de donner une liste d’astuces permettant des implémentations efficaces, on veut plutôt voir quels sont les problèmes intrinsèques à la pratique, et dégager des idées générales pour les résoudre. Ces idées sont donc plus des conditions nécessaires pour toute implémentation du modèle général voulant respecter les objectifs annoncés en 4.2..

5.1. Quand doit-on pouvoir agir

Nous avons vu que l’oracle agit en appliquant une fonction f_{oracle} sur (E_{i}, <_{E_{i}}). Un de nos objectifs est de ne pas restreindre le pouvoir de l’oracle (par exemple si on lui posait simplement des questions fixées, son pouvoir pourrait être limité). Ainsi, pour que l’oracle puisse contrôler totalement les choix du calculateur, il faudrait qu’avant chaque choix de nœud à traiter, l’oracle puisse applique f_{oracle}. Or il est impensable d’envisager une telle méthode car l’application de f_{oracle} à un coût, et si l’on alternait ainsi les appels, le surcoût de l’interaction serait énorme, ce qui contredit un de nos objectifs. Il faut donc introduire un contrôleur qui imposera l’application de f_{oracle} à une fréquence (pouvant être variable) déterminée.

5.2. Définition d’un état en pratique

En pratique, les ensembles successifs E_{i} sur lesquels le calculateur fait des insertions et des extractions, seront représentés par UN conteneur C, qui fournira un insérer() et un extraire(). On va donc voir quelles fonctions ce C doit fournir en pratique pour permettre l’interaction.

5.3. f_{oracle} en pratique

5.3..1 La nature de f_{oracle}

Pour le moment f_{oracle} est une fonction «mathématique» qui associe à (E_{i}, <_{E_{i}}) un (E′_{i}, <_{E′_{i}}). On se doute que pour des raisons pratiques (problème de synchronisation, de cohérence), le calculateur s’arrêtera pendant l’application de f_{oracle}. Mais comment faire pour que l’oracle humain puisse appliquer son f_{oracle}? Une première solution consisterait à, pendant que le calculateur est donc arrêté, montrer les éléments à l’oracle pour qu’il les classe, « à la main». Bien sûr cette méthode viole totalement notre objectif de nonsurcoût, et de plus nous voulions que quand l’oracle n’interagit pas, le calculateur reste efficace, et donc ne soit surtout pas bloqué ! Il faut donc qu’à tout moment l’oracle soit capable de fournir f_{oracle} et de l’appliquer, i.e. que f_{oracle} soit une «vraie» fonction, au sens informatique du terme. Il faut donc pouvoir expliciter cette fonction.

5.3..2 Définir f_{oracle}

De quoi avons nous besoin pour définir f_{oracle}

Pour que l’oracle humain puisse donc fournir à chaque instant une «vraie» fonction f_{oracle}, il faut qu’il puisse voir (E_{i}, <_{E_{i}}). Pour exhiber un ensemble et son ordre total, C doit donc pouvoir effectuer un «montrerdans-l’ordre()» qui est tel que, si au pas numéro i, C ⟺ (E_{i} = x_{1}, ..., x_{n}, <_{E_{i}}), avec x_{j_{1}} <_{E_{i}} ... <_{E_{i}} x_{j_{n}} alors montrer dans l’ordre() doit exhiber x_{j_{1}} puis x_{j_{2}} puis .. x_{j_{n}}.

Remarque 5.3..2.1 On pourrait croire qu’il est inutile d’avoir imposé ce «montrer-dans-l’ordre()» pour voir l’état. En effet, pourquoi ne pas se contenter d’utiliser extraire() ? Pour comprendre pourquoi cela ne marche pas, imaginons que C soit un tableau à deux cases, tel que l’élément dans la première case a \frac{1}{4} d’être extrait, et celui dans la deuxième case \frac{3}{4}. L’oracle peut donc vouloir permuter les deux éléments. Mais pour savoir si il veut le faire, il faudrait qu’il puisse voir quel élément est dans la case 1, et quel élément est dans la deuxième. Ici, «montrer-dans-l’ordre()» pourrait satisfaire à ce besoin, alors que en recevant un élément de extraire(), on ne pourrait pas savoir d’où il vient !

Poursuivons sur l’affichage : pour une raison évidente de non-surcoût, le calculateur ne peut pas communiquer tous les E_{i}, <_{E_{i}}. Il faut donc n’utiliser «montrer-dans-l’ordre» qu’à une certaine fréquence.La conséquence de ceci est que l’oracle n’aura qu’une vision retardée de l’état du calculateur (cf figure 5.2).

Une façon de représenter f_{oracle}

Puisque l’on pense l’application de f_{oracle} au sens informatique du terme, il faut donc régler trois points – comment communiquer le paramètre E_{i}, <_{E_{i}}

– comment représenter la décision de vouloir changer E_{i}, <_{E_{i}} en E′_{i}, <_{E′_{i}}

– comment récupérer le résultat E′_{i}, <_{E′_{i}} Pour le premier point, il suffit d’utiliser le «montrer-dans-l’ordre()» fourni pas C. Pour le dernier point, on va imposer à C de pouvoir faire une «affectation-dans-l’ordre()». Pour le second, une solution consiste à

– avoir à tout moment un critère de comparaison <_{oracle} (ordre total)

– utiliser un conteneur C_{oracle} qui implémente cet ordre total, i.e. qui sait «insérer-en-classant()», et «donner-majorant()»

– permettre de changer <_{oracle} via un «changer-<_{oracle}»

– avoir à tout moment une condition ϕ_{suppression} qui indique quels éléments on veut supprimer

– permettre de changer ϕ_{suppression} via un «changer-< ϕ_{suppression}» Ainsi f_{oracle} serait constituée des appels successifs à «montrer-dans-l’ordre()», contrôler ϕ_{suppression}, «inséreren-classant()», «donner-majorant()», «affectation-dans-l’ordre()».

5.4. Bilan

On va donc voir que les solutions proposées dans ce «modèle pratique» vont permettre le respect des objectifs.

Pour ce qui est de la réactivité, cela va dépendre du contrôleur. Plus il sera adapté pour être réactif, plus il y aura de surcoût. Concernant les problèmes de coût liés à la synchronisation, on constate que notre modèle peut bien être très asynchrone, car la synchronisation ne s’effectuera que pendant l’application de f_{oracle} (cf figure 5.1 et 5.2)

Fig. 5.1 – Bilan de l’interaction

Fig. 5.2 – Un exemple d’interaction

Concernant le pouvoir de l’oracle, on constate que plus il pourra appliquer f_{oracle}, plus il aura de pouvoir. Cela dépend donc là aussi de la politique du contrôleur.

Enfin, on peut remarque qu’une façon simple de se protéger des oracles malicieux est d’interdire la suppression d’éléments. On est alors sûr d’explorer entièrement l’arbre des solutions, même si l’oracle ne cesse de donner de mauvais chemins d’exploration.

Instanciation du modèle pour le problème du puzzle

Conformément à ce qui a été annoncé au 4., nous avons choisi de traiter le problème du puzzle, qui on le rappelle est un bon exemple dans lequel l’expert a une connaissance supplémentaire, spécifique à l’instance en cours de résolution. L’implémentation (réalisée en C++) ne sera pas extrêmement détaillée car l’objectif n’était pas de réaliser un programme optimisé pour l’exemple du puzzle, mais bien au contraire de montrer que même une implémentation «naïve» permet de mettre en évidence l’intérêt de l’interaction. Le projet a donc été codé avec un esprit de simplicité et de «généralité».

6.1. Présentation de l’implémentation

Le principe général de l’implémentation respecte le modèle présenté au chapitre 5. Nous nous contenterons donc de présenter les principaux choix effectués.

6.1..1 Structure générale

Pour ce qui est des classes, on peut en citer trois principales : Conteneur_{Local} et Conteneur_{Oracle} qui représentent respectivement le C et le C_{oracle} du modèle pratique, ainsi qu’une classe Conteneur_{Interactif} qui permet de synchroniser les deux. Quand au parallélisme, deux fils d’exécution seront créés pour que l’on puisse à la fois permettre au calculateur d’exécuter son algorithme et être à l’écoute des ordres de l’oracle-utilisateur.

6.1..2 Côté calculateur

Nous avons choisi pour la classe Conteneur_{Local} d’utiliser une pile. En effet, on aimerait que, après avoir indiqué au calculateur les premiers choix, il explore en profondeur le sous arbre des solutions indiquées. De plus, cette exploration en profondeur reflète bien les conséquences de bons ou de mauvais choix. D’autre part, on pourra facilement fournir des fonctions correspondant à «montrer-dans-l’ordre()» et «affectationdans-l’ordre()».

Le contrôleur (qui permet de savoir quand on doit prendre en compte les décisions de l’oracle) sera ici un simple compteur, décrémenté à chaque pas de l’algorithme (i.e. à chaque extraction ou «pop()» ici), et remonté à une certaine valeur après chaque interaction.

6.1..3 Côté oracle

La classe Conteneur_{Oracle} comporte tout d’abord une file de priorité, qui permet donc de fournir l’équivalent d’un «insérer-en-classant()» et d’une «donner-majorant()». Le <_{oracle} est donc la fonction de comparaison f_{comparaison} de cette file de priorité.

Pour pouvoir «changer-<_{oracle}», l’idée adoptée est que f_{comparaison} se serve d’un objet Info_{P riorite} (qui répertorie les critères imposés par l’oracle), et que «changer-<_{oracle}» soit donc un simple ajout/retrait d’un élément de ce Info_{P riorite}. On ne va donc pas changer complètement la fonction f_{comparaison} (en insérant le code d’une autre fonction par exemple). On peut donc légitimement se demander si l’un de nos objectifs n’a pas été violé : le pouvoir de l’oracle ne sera-t-il pas trop limité ? Va-t-on perdre en généralité ? Il se trouve que ce choix n’est pas trop restrictif, du fait de la pertinence des critères que l’on va répertorier dans Info_{P riorite}. En effet, même si l’on ne sait pas comment résoudre un problème efficacement dans le cas général, on est souvent capable d’anticiper quelles informations seront déterminantes pour en accélérer la résolution. Les intuitions d’un expert extérieur face à un problème d’optimisation combinatoire seront très souvent soit une solution locale, soit des bornes pour les valeurs de certaines variables, soit une corrélation entre plusieurs variables. Ainsi, selon le problème pratique considéré, il suffit avant de lancer la résolution interactive d’incorporer à l’objet Info_{P riorite} des fonctionnalités permettant de stocker ces informations. Par exemple pour le puzzle, on peut prévoir qu’il sera facile pour l’utilisateur de voir que certaines pièces doivent être dans certaines zones, que certaines pièces doivent être appariées. Dans le programme réalisé, on s’est donc contenté de pouvoir ajouter à l’objet Info_{P riorite} des contraintes du type «telle pièce doit être à tel endroit».

Pour le ϕ_{suppression} et le «changer-< ϕ_{suppression}», l’idée est la même : la fonction f_{vérifie ϕ} utilisera un objet Info_{Suppression}.

Concernant ces deux points délicats que sont «changer-<_{oracle}» et «changer-< ϕ_{suppression}», on pourrait se demander si l’idée pratique proposée (l’utilisation de Info_{P riorite} et de Info_{Suppression}) ne pose pas un autre problème : certes la prévision de critères AVANT l’exécution n’est pas si restrictive qu’il y paraît, cependant, si l’on imagine qu’après un très long calcul (plusieurs semaine par exemple), on s’aperçoit qu’il aurait fallu ajouter d’autres critères, il ne faudra pas recommencer le calcul depuis le début ! Ce cas est d’ailleurs d’autant plus important que les problèmes que l’on va résoudre interactivement nécessitent en général de très gros calculs. La réponse à cela est qu’il sera toujours possible d’envisager une méthode pour cette fois ci changer du code concernant Info_{P riorite} (ou même f_{comparaison}), il suffira de «prévenir» le calculateur pendant la mise à jour côté oracle. On pourrait aussi tout simplement créer des fonctions de «load» et de «store» permettant d’interrompre le calcul sans tout perdre. En résumé, ce problème semble soluble car le code du calculateur et de l’oracle sont séparés.

Un dernier point doit être discuté : l’affichage. En effet, pour que l’interaction soit «bonne», il faut que l’oracle puisse avoir une vision intelligente de l’état, qu’il puisse voir par exemple les solutions partielles qui l’intéresse, ou celles qui seront prochainement traitées par le calculateur. Pour ce faire, nous avons ajouté au Conteneur_{Oracle} une fonction f_{vérifie affichage}, utilisant un objet Info_{Affichage}, permettant de n’afficher que les puzzles respectant les critères mentionnés dans Info_{Affichage}. Le critère initialement prévu ici sera simplement la profondeur, car il est souvent utile de considérer les solutions partielles qui ont le plus de fils.

6.1..4 Interface entre les deux parties

La classe Conteneur_{Interactif} permet de régler les problèmes de contention : c’est à travers cette classe que l’utilisateur agit sur le Conteneur_{Oracle}, et à travers cette classe que l’on applique le f_{oracle} (grâce à une fonction nommée merge). Ainsi, on pourra être sûr que l’utilisateur n’est pas en train de faire des modifications pendant que le calculateur applique le f_{oracle}. La figure 6.1 résume l’organisation de ces classes.

6.2. Les difficultés liées à l’interprétation des résultats

Il y a donc deux choses principales à étudier : le surcoût et le gain de performance liés à l’interaction. Nous allons voir en quoi il est délicat de faire des mesures pour ce type de résultats.

Fig. 6.1 – Bilan de l’implémentation

Pour le premier point, on pourrait par exemple comparer les performances de l’algorithme seul (i.e. quand le contrôleur n’ordonne jamais de prendre en compte l’oracle) et de la résolution interactive sans aide de l’oracle (i.e. quand on comptabilise en plus le temps passé à vérifier les décisions de l’oracle). Cependant, pour pouvoir faire des mesures intéressantes concernant la «performances de l’algorithme seul», il faudrait au moins faire varier l’algorithme du calculateur, son conteneur, ainsi que tester un grand nombre d’instances, et concernant le coût des vérifications des décisions de l’oracle, on peut noter que celui dépend énormément de la façon de faire le merge, et de la politique du contrôleur. De plus, de nombreuses idées permettraient d’accélérer la résolution interactive. Parmi ces idées, certaines sont clairement des «astuces», trop spécifiques donc, et d’autres sont plus des principes généraux qui s’incorporeraient bien ici (cf «perspectives» en 4.). Or cette première implémentation, dans un soucis de généralité, n’utilise aucune de ces idées. Il aurait donc fallu faire varier beaucoup de paramètres pour obtenir ce premier type de mesures, ce qui n’a pas pu être fait faute de temps.

Pour le second point, en plus des paramètres déjà mentionnés ci dessus, il est évident que le gain lié à l’interaction dépend principalement de la manière d’agir de l’oracle, ce qui est difficile à classifier (comment savoir à quel point les conseils de l’oracle étaient bons, à quel point leur exploitation a été satisfaisante ?). Cependant, même si des mesures générales sont difficiles à mener, nous avons pu observer sur notre exemple un impressionnant gain de temps grâce à l’intervention d’un oracle non malicieux lors de la résolution de «grosses» instances. Dans la section suivante seront donc exposées ces mesures encourageantes.

6.3. Mesures d’un test simple

Nous avons donc testé le cas dans lequel l’oracle ne donne que des informations justes (il connaît en fait la solution dès le départ !). L’algorithme du calculateur utilisé pour les mesures est une bête exploration (exhaustive) en profondeur : l’algorithme prend à chaque pas la première pièce disponible et essaye la placer partout où cela est possible.

On peut donc voir sur le schéma 6.2 le temps de résolution seul en trait plein (correspondant dans notre implémentation à une valeur de compteur «infinie» ) d’une part, et celui avec un certain nombre de conseils de l’oracle (en pointillés épais avec un conseil, et en pointillés fins avec deux conseils), le tout selon le nombre de pièces du puzzle. «Un conseil» signifie que l’on a indiqué au calculateur la position d’une pièce. Chaque point correspond en fait à une moyenne sur plusieurs instances différentes de même taille.

Fig. 6.2 – Temps de résolution en secondes en fonction du nombre de pièces

Plusieurs choses sont à remarquer pour interpréter correctement ces résultats. Pour les petites instances (de taille inférieure ou égale à 15), on ne peut pas gagner en interagissant, car le temps qu’il faut à l’utilisateur pour communiquer un conseil est de l’ordre de ce temps de résolution de l’algorithme seul. Concernant les mesures obtenues avec intervention de l’oracle, il faut souligner que l’influence des ses conseils dépend (entre autres) du moment ou l’oracle agit, et de la pièce concernée : si l’on conseil très tôt de placer une des "premières" pièce au bon endroit, on perd quasi instantanément un degré de factorielle, alors que si l’on attend longtemps et que la pièce concernée est choisie en dernier par l’algorithme, la quantité de puzzles à trier à chaque interaction est très grande et l’élagage est moindre. Il doit donc être précisé que lors des mesures «avec» oracle, les conseils ont été donnés le plus tôt possible, et concernant les pièces les plus utiles.

Perspectives et conclusion

Nous avons donc vu que même une implémentation simple, respectant le modèle pratique, permet d’accélérer la résolution d’un problème NP-complet. Cependant, comme nous l’avons précisé dans la section 6.2., de nombreuses optimisations sont envisageables.

Un première chose à discuter est la politique du contrôleur. En effet, pour le moment on se contente de vérifier les décisions de l’oracle à une fréquence régulière, mais il serait bon d’envisager un schéma de contrôle beaucoup plus souple. On pourrait pour cela utiliser des techniques de contrôle amorti, afin de minimiser le surcoût de l’interaction tout en restant réactif.

D’autre part, lorsque le calculateur interagit avec l’oracle (i.e. lorsqu’il fait «trier ses calculs»), il doit pour l’instant attendre que l’oracle ai terminé avant de pouvoir reprendre l’exécution de son algorithme. Il serait donc très intéressant de recouvrir ce temps de traitement de l’oracle, en laissant par exemple au calculateur du travail à effectuer.

Une autre perspective clef est le parallélisme. En effet, le modèle présenté au chapitre 5 peut parfaitement s’adapter à plusieurs calculateurs. On pourrait alors considérer que l’oracle détient un ensemble de calculs à effectuer, et qu’il les distribue aux calculateurs venant interagir avec lui. On peut même envisager d’étendre encore ce modèle pour pouvoir utiliser plusieurs oracles.

L’interaction calculateur-oracle s’avère donc être puissante et prometteuse, tant au niveau théorique que sur notre exemple pratique.

Résumé : L’objectif de ce stage est de présenter la complexité interactive et de montrer son application sur un problème simple, pour bien distinguer les difficultés propres à cette approche en général des difficultés spécifiques à un problème réels trop particulier.

Dans ce cadre nous faisons d’abord un état de l’art de la complexité interactive. Puis nous étudions la problématique de l’interaction au sens pratique, c’est-à-dire pour exploiter toutes les ressources du calculateur sans se bloquer dans l’attente d’une réponse de l’oracle. Enfin nous présentons sur un problème facilement compréhensible une mise une œuvre qui respecte le modèle d’interaction non-bloquante présenté.