Écrire un vérificateur

Le certificat est une couleur par sommet ; le vérificateur contrôle deux choses, et seulement deux.

/* Verifie qu'une coloration est propre.
   Entrees : n sommets, m aretes (u[i], v[i]), une couleur par sommet, k couleurs.
   Sortie  : true ssi toutes les couleurs sont dans [0, k[ et aucune arete
             ne joint deux sommets de meme couleur.
   Complexite : Theta(n + m) -- une seule passe sur les sommets, une sur les aretes. */
bool coloration_propre(int n, int m, const int u[], const int v[],
                       const int couleur[], int k) {
    assert(n >= 0 && m >= 0 && k >= 1);
    for (int i = 0; i < n; i = i + 1) {
        if (couleur[i] < 0 || couleur[i] >= k) { return false; }
    }
    for (int a = 0; a < m; a = a + 1) {
        if (couleur[u[a]] == couleur[v[a]]) { return false; }
    }
    return true;
}

La première boucle est celle qu'on oublie. Sans elle, un certificat qui attribuerait la couleur $7$ à chaque sommet serait accepté pour $k=3$ : aucune arête ne joindrait deux couleurs différentes, et l'on aurait « prouvé » qu'un graphe quelconque est $3$-coloriable. Un vérificateur doit contrôler que le certificat est bien formé avant de contrôler qu'il convient — sans quoi il ne vérifie rien.

L'exécution sur le graphe de Petersen ($10$ sommets, $15$ arêtes) donne :

L'asymétrie, en chiffres. Trouver a demandé $3544$ colorations essayées ; vérifier en demande une et coûte $15$ comparaisons. Sur un graphe à $50$ sommets, la recherche exhaustive demanderait $3^{50}\approx 7\cdot 10^{23}$ essais, et la vérification resterait proportionnelle au nombre d'arêtes.

C'est très exactement la définition de $\mathsf{NP}$, rendue concrète : le certificat tient en $n$ entiers, sa vérification en deux boucles. Rien d'autre n'est exigé.