Certificat (complexité)

En informatique théorique, un certificat est, de façon simplifiée, une information permettant de trouver plus facilement le résultat d'un calcul. Cette notion apparait dans notamment deux aspects de l'étude de complexité en informatique : l'étude des classes de complexités et la complexité d'évaluation de fonction booléen .

Certificat dans le domaine des classes de complexités

Définition informelle

Étant donné un problème de décision, un certificat est une information que l'on ajoute à une donnée du problème, pour certifier (au sens où la vérification devient «facile»), que la réponse au problème pour cette donnée soit «oui» ou «non».

Exemples

Nombre composé :

Pour certifier qu'un nombre est composé (i.e. n'est pas premier), il suffit d'exhiber un facteur. Par exemple, pour certifier que 15 est un nombre composé, le nombre 5 est un certificat: il suffit alors de vérifier que 5 divise 15.

Coloration de graphe

Pour vérifier qu'un graphe non orienté est colorable avec trois couleurs, c'est-à-dire que l'on peut colorier chaque sommet d'une couleur de façon que deux sommets voisins ne soient pas de la même couleur, il suffit d'exhiber une telle coloration. Pour certifier qu'un graphe est colorable, une coloration est un certificat: il suffit alors de vérifier que la coloration attribue bien des couleurs différents à deux sommets voisins.

Définition formelle avec la classe NP

Sur un alphabet $\Sigma$ , un langage $L$ est dans NP s'il existe un polynôme $P$ et un langage $B$ dans P, tels que pour un mot $x$ de taille $n$ : $x\in L\Leftrightarrow \exists u\in \Sigma ^{P(n)},(x,u)\in B$ ^[1].

L'interprétation est la suivante: $x$ est dans le langage L si et seulement il existe un certificat de taille polynomiale.

Certificat dans le domaine des complexités d'évaluation de fonctions

Contexte et modèle

On se place dans le contexte d'une fonction booléen, c'est-à-dire $f:\{0,1\}^{n}\mapsto \{0,1\}$ . Le but est d'estimer la complexité de l'évaluation d'une telle fonction.

On a en notre entrée $x=(x_{1},\dots ,x_{n})$ , est la complexité est le nombre de variables à évaluer dans le pire cas.

Voir Arbre de décision

Exemple

Pour évaluer $f(x_{1},x_{2})=1$ aucune évaluation est nécessaire.

À l'opposé $f(x_{1},x_{2})=x_{1}\wedge x_{2}$ nécessite d'évaluer toutes ces variables.

Certificat

Idée du certificat

Pour la fonction $OR_{n}$ , la fonction $OR_{n}$ sur $n$ bits. Le fait de dire que $x_{1}=1$ cela permet de décider que $OR_{n}(x)=1$ .

Pour la fonction $TRIBES_{n}(x)=AND(Or(x_{1},\dots x_{n}),Or(x_{n+1},\dots x_{2n}),\dots ,Or(x_{n(n-1)},\dots x_{n^{2}}))$ . Pour savoir que $TRIBES_{n}(x)=0$ il suffit de connaitre un "bloc" où tous les entiers valent 0. Pour savoir que $TRIBES_{n}(x)=1$ il suffit de connaitre un 1 pour chaque "bloc".

Assignement partiel

Un assignement partiel est un élément de $\rho \in \{0,1,*\}^{n}$ . On désigne par $|\rho |$ le nombre de 0 et de 1.

Par exemple $|(0,0,*,*,*,1)|=3$ .

Si le $i-$ ième élément vaut 0 (resp. 1) alors on va étudier les entrée lorsque $x_{i}=0$ (resp. 1). Lorsque cette propriété est toujours vrai, on notera $\rho \subset x$

Définition : $\rho$ est un 0-certificat si et seulement si pour tous x tels que $\rho \subset x$ , alors $f(x)=0$ . De même on définit la notion de -certificat.

On définis la complexité de certificat : $C(f,x)=\min \limits _{\rho \subseteq x}\{|\rho |,\rho {\text{ un certificat pour }}f\}$ et on étend cela pour tous éléments en prenant 'les pires cas' :

$C_{0}(f)=\max \limits _{x\in f^{-1}(0)}C(f,x)\quad et\quad C_{1}(f)\max \limits _{x\in f^{-1}(1)}C(f,x)\quad et\quad C(f)=max\{C_{0}(f),C_{1}(f)\}$ ^[2].