Université BORDEAUX 1 | U.F.R. Mathématiques et Informatique |
MAI 932 EX2 (épreuve de J.Bétréma) | 23 janvier 2004 |
Durée: 1 heure 30
Tous documents interdits.
Voir le corrigé.
Voir le corrigé.
Prouver que ZPP est l'intersection de RP et co-RP.
Voir l'énoncé.
2 points. PRIME appartient à NP, car n est premier si et seulement si le groupe multiplicatif des entiers modulo n est un groupe cyclique ; un certificat consiste donc en un générateur a de ce groupe, accompagné de la décomposition en facteurs premiers de n - 1, et des certificats de primalité de ces facteurs. La vérification du certificat consiste à calculer a n-1 modulo n (qui doit être égal à 1), en utilisant un algorithme d'exponentiation rapide, puis a (n-1)/d modulo n (qui doit être différent de 1), pour chaque diviseur premier d de n - 1 ; il faut aussi vérifier que la décomposition en facteurs premiers de n - 1 est correcte, en calculant le produit des facteurs, et en vérifiant récursivement la primalité de chaque facteur. C'est la partie récursive de l'algorithme qui rend délicate la preuve que cette vérification est polynomiale, mais le résultat est vrai.
Note : dans les conditions de l'examen, les deux points étaient attribués dès que le principe du certificat était décrit, sans entrer dans les détails ci-dessus.
2 points. D appartient à co-NP, car pour prouver que n ne possède pas de diviseur inférieur à k, on peut utiliser comme certificat la décomposition en facteurs premiers de n, accompagnée d'un certificat de primalité (voir question 1) de chacun des facteurs. Note : ce résultat utilise simplement l'appartenance de PRIME à NP, il est inutile de savoir que PRIME appartient à P (algorithme AKS).
Note : une grande partie de la cryptologie moderne repose sur la difficulté du problème de la factorisation, et donc de D ; elle repose aussi sur la facilité (relative) de PRIME (test de primalité), car pour produire de grands nombres difficiles à factoriser, il faut produire efficacement de grands nombres premiers. Confondre les classes de complexité de ces deux problèmes est donc inadmissible dans le contexte de ce master.
Voir l'énoncé.
4 points. RP est la sous-classe de NP obtenue en exigeant qu'il existe un nombre significatif de certificats, de telle sorte que la recherche au hasard d'un tel certificat ait une probabilité significative de succès. Un langage L est dans RP si et seulement s'il existe un algorithme probabiliste polynomial A tel que :
x appartient à L
⇒
proba [ A (x, r) = 1 ]
> λ > 0
x n'appartient pas à L
⇒
proba [ A (x, r) = 0 ] = 1
où λ désigne une constante (qu'on peut choisir égale à 1/2), et r une variable aléatoire, qui sert de certificat pour x lorsque A (x, r) = 1 ; les probabilités font référence à cette variable aléatoire r, et comme il s'agit de probabilités discrètes, la seconde condition peut aussi s'écrire :
x n'appartient pas à L ⇒ ∀r A (x, r) = 0
ou encore, en prenant la contraposée
A (x, r) = 1 ⇒ x appartient à L.
Note : lorsque x n'appartient pas à L, autrement dit lorsque la "bonne réponse" est 0, l'algorithme A répond toujours 0 ; il ne faut pas en déduire malencontreusement que lorsque A répond 0, c'est une réponse "sûre" ; au contraire, comme on vient de le voir, c'est la réponse 1 qui est sûre, même si c'est déconcertant à première vue !
Terminologie : on peut remplacer le langage L par sa fonction caractéristique χ , et énoncer, de façon équivalente, que le problème de décision χ est dans RP si et seulement s'il existe un algorithme probabiliste polynomial A tel que :
χ (x) = 1
⇒
proba [ A (x, r) = 1 ]
> λ > 0
χ (x) = 0
⇒
∀r A (x, r) = 0
Pour comparer rigoureusement RP et NP, on peut rappeler que L est dans NP si et seulement s'il existe un vérifieur polynomial V tel que :
x ∈ L ⇔ ∃c V (x, c) = 1
où c désigne un certificat. Démontrer l'inclusion RP ⊂ NP revient à utiliser A comme vérifieur, et à remarquer que, lorsque x ∈ L :
proba [ A (x, r) = 1 ] > λ > 0 ⇒ ∃r A (x, r) = 1
tandis que réciproquement, comme on l'a remarqué ci dessus, on a :
A (x, r) = 1 ⇒ x ∈ L.
5 points. Montrons d'abord ZPP ⊂ RP. Soit L un langage dans ZPP, et A un algorithme probabiliste polynomial avec zéro erreur qui reconnaisse L ; on peut alors construire un nouvel algorithme B comme suit :
B (x, r) = |
ì í î |
A (x, r) si A (x, r) = 0 ou 1 |
0 si A (x, r) = 2 |
Alors, si x ∈ L, A (x, r) vaut 1 ou 2, donc :
proba [ B (x, r) = 1 ] = 1 - proba [ A (x, r) = 2 ] > 1 - λ
Inversement, si x n'appartient pas à L, A (x, r) vaut 0 ou 2, donc B (x, r) = 0, ce qui achève de prouver L ∈ RP. On montre de la même façon ZPP ⊂ co-RP : il suffit de choisir, ci-dessus, B (x, r) = 1 lorsque A (x, r) = 2.
Reste à montrer, réciproquement, RP ∩ co-RP ⊂ ZPP. Soit L un langage dans RP ∩ co-RP, reconnu par deux algorithmes probabilistes polynomiaux A et B, correspondant aux définitions respectives de RP et co-RP ; en particulier, comme on l'a vu dans la réponse à la première question, les réponses A = 1 et B = 0 sont sûres, autrement dit :
A (x, r) = 1
⇒
x appartient à L
B (x, r) = 0
⇒
x n'appartient pas à L
On peut alors construire un nouvel algorithme C comme suit :
C (x, r) = |
ì ï í ï î |
0 si B (x, r) = 0 |
1 si A (x, r) = 1 | ||
2 si A (x, r) = 0 et B (x, r) = 1 |
C fournit donc une réponse sûre lorsque celle-ci vaut 0 ou 1 ; reste à borner la probabilité de la réponse 2 ; supposons x ∈ L (l'autre cas est symétrique), d'où B (x, r) = 1, et :
proba [ A (x, r) = 1 ] > λ
proba [ C (x, r) = 2 ] = proba [ A (x, r) = 0 ] < 1 - λ