Notes of Bernard Chazelle’s lecture nr 3

I missed lecture nr 2 (due to perturbation in pubic transports). It was filmed. The video will be downloadable on Collège France website.

Interactive proofs and algorithmic epistemology

Biblio : Arora-Barak

Né de la crypto. Aujourd’hui, le cours est orienté vers les preuves à divulgation nulle, et PCP. Vastes sujets.

1. Preuves

1.1. Les classes P et NP

J’emploie les notations d’Arora-Barak.

NP : langages tels que {\forall x}, {x\in L \Leftrightarrow\exists y} tel que {A(x,y)=1}. {A} est un algorithme qui tourne en temps polynomial en {|x|}.

On pense à {y} comme à une preuve de l’énoncé {x\in L}.

Example 1 3-coloriages. Une preuve de 3-colorabilité, c’est un coloriage.

Problèmes NP-complets.

1.2. Preuves intéractives

Elles diffèrent en deux points,

  1. C’est un dialogue.
  2. Il y a des tirages au hasard.

Intuition (de prof) : le dialogue facilite la transmission de la preuve.

Intuition (de physicien) : principe d’incertitude d’Heisenberg : une fonction et sa transformée de Fourier ne pas \^etre simultanément à support borné. L’alea délocalise la preuve. Si erreur il y a, elle va \^etre répandue partout dans le texte, donc aisément détectable.

Je suis le prouveur, vous le vérificateur. Je sais répondre instantanément à toutes les questions, je suis tout puissant. Vous utilisez des bits aléatoires. Pour simplifier (pas indispensable), j’ignore le résultat de vos tirages. Vous \^etes limité au calcul polyn\^omial. Cette asymétrie est nécessaire.

Autre asymétrie : Evidemment, P=coP. Mais est-ce que NP=coNP ? Probablement non. Il semble difficile de prouver qu’un graphe n’est pas 3-coloriable, qu’un entier est premier (ce problème est P), qu’un jeu a une stratégie gagnante (ce problème est P-SPACE complet), qu’un piano peut \^etre sorti d’une salle (ce problème est P-SPACE complet).

Theorem 1 (Shamir 1992) IP=PSPACE. Autrement dit, pour tout problème de la classe PSPACE, un prouveur peut convaincre un vérificateur, en temps polynomial, qu’il détient la solution.

La classe PSPACE est gigantesque. Cela donne une idée de la puissance des protocoles intéractifs.

1.3. Preuves à divulgation nulle

Une preuve à divulgation nulle, est intéractive, probabiliste, et en plus, ne révèle qu’un bit.

Example 2 3-coloriages. Une preuve de 3-colorabilité consiste à tirer une ar\^ete au hasard, demander au prouveur les deux couleurs des extrémités. Et recommencer.

En faisant l’expérience 100{|E|} fois, la probabilité d’erreur (sur la conclusion : 3-coloriable ou non) devient infime. Cela révèle plein de choses sur le coloriage.

On modifie le procédé : entre deux tirages, on effectue une permutation aléatoire des sommets. Alors le vérificateur n’apprend plus rien d’autre que l’unique bit : le graphe est 3-coloriable ou non. En effet, les paires de couleurs qu’il a observées sont tirées selon une distribution qu’il peut parfaitement simuler tout seul.

Puis-je cacher les couleurs ? Mettre chaque sommet dans une enveloppe, et remettre le tout au vérificateur. Comment le faire électroniquement ? Avec une fonction à sens unique. RSA, très utilisé, n’est probablement pas à sens unique, mais on croit que de telles fonctions existent.

Theorem 2 Sous l’hypothèse de l’existence de fonctions à sens uniques (problème ouvert), tout problème de la classe NP possède des preuves à divulgation nulle.

2. PCP

La motivation est différente. Vous avez un gros calcul à faire, vous le sous-traitez, comment avoir rapidement une assurance que le résultat est correct. Cette fois, c’est le prouveur qui souhaite convaincre, et le vérificateur qui résiste (il n’a pas envie d’y consacrer de gros moyens).

Definition 3 PCP({\log n}, 1) = ensemble des langages pour lesquels

  1. Si {x\in L}, il existe une preuve de ce fait qui peut \^etre vérifiée en temps polyn\^omial en lisant un nombre borné de bits de la preuve, en utilisant {O(\log n)} bits aléatoires.
  2. Si {x\notin L}, il n’existe pas de preuve, avec probabilité d’erreur {<1/2}.

Theorem 4 (Arora,…) PCP({\log n}, 1) = NP.

2.1. Formulation équivalente

Il y a un compilateur qui transforme tout système d’équations quadratiques modulo 2 sans solution en un système dont au plus une fraction {1-\epsilon} sont satisfiables simultanément.

Voir l’exposé de Claire Mathieu, qui va développer cet aspect optimisation.

2.2. Preuve

Preuve du fait que {n} points de {{\mathbb R}^3} sont coplanaires : pour chaque {(x,y)}, je retourne {z=f(x,y)}, où {f} est linéaire.

Supposons que les points sont coplanaires mais je triche. Ma fonction {z=f(x,y)} n’est pas linéaire. Tirez deux points et demandez au prouveur le {z} de ces trois points. Vérifiez que {f} se comporte comme une fonction linéaire. On prouve aisément que si le test est positif avec forte probabilité, la surface est un plan avec une erreur très faible. La méthode donne une interpolation linéaire de {f} (décodeur). Reste à vérifier, par un nombre borné d’appels à {f}, si le plan correspondant passe par les {n} points. Prenez un barycentre des {n} points à poids aléatoire. M\^eme si un seul point du nuage n’est pas sur le plan, le barycentre va \^etre affecté. En demandant au prouveur

Un système quadratique, c’est un système linéaire en {u\otimes u}. Cette méthode prouve que NP=PCP(poly({n}),1).

2.3. Amélioration

Pour passer de PCP(poly({n}),1) à PCP({\log n},polylog({n})), on améliore le décodeur.

La dernière étape, c’est l’auto-réductibilité. C’est un mécanisme, assez unique (rare en maths, peut-\^etre présent en logique), qui prend la démonstration précédente dans son ensemble, effectue dessus une opération qui en améliore la performance.

2.4. Commentaire final

Les points du nuage, ce sont les contraintes logiques, les garde-fou, indépendants de la preuve. C’est la garantie que les calculs sont faits par une machine de Turing correcte.

Problème ouvert, en pratique : Des PCP de niveau élevé, i.e. qui ne se placent pas au niveau des chaînes de bits, mais manipulent des types plus sophistiqués.

About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See http://www.math.ens.fr/metric2011/
This entry was posted in Course and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s