Chapitre 8 : Classes P et NP

Table des matières

Chapitre 10 : Algorithmes probabilistes
et fonctions à sens unique

Chapitre 9 : Problèmes NP-complets

  1. Formules booléennes
    1. Forme normale conjonctive
    2. Egalité
    3. Tautologies
    4. SAT
  2. Réductions
  3. SAT est NP-complet
    1. Théorème de Cook et Levin
    2. Circuits logiques
    3. CNF est NP-complet
    4. 3-CNF est NP-complet
  4. Problèmes difficiles sur les graphes
    1. Colorations
  5. Problèmes difficiles en arithmétique
    1. SUBSET-SUM
  6. Complémentaires des problèmes NP-complets

1. Formules booléennes

Une formule booléenne ressemble à une expression arithmétique, avec deux différences :

A toute formule booléenne Φ est associée une table de vérité, qui donne la valeur de Φ pour chacune des 2n valeurs possibles du vecteur x = x1xn ; mais il existe de nombreuses formules distinctes ayant même table de vérité, il ne faut donc pas confondre l'une et l'autre.

1.1. Forme normale conjonctive

Il existe deux classes particulières importantes de formules :

Les lois de Morgan ( p et q désignent des formules quelconques) :

¬ ( pq ) = ¬p ∧ ¬q , ¬ ( pq ) = ¬p ∨ ¬q

montrent que la négation d'une forme normale conjonctive est une forme normale disjonctive, et vice-versa. Malgré cette symétrie, la forme normale conjonctive est beaucoup plus utile, car chaque clause exprime une contrainte, et une forme normale conjonctive exprime un ensemble de contraintes à satisfaire simultanément.

Notons que toute formule Φ possède une forme normale disjonctive (respectivement conjonctive) ; une façon de l'obtenir est d'associer une conjonction à chaque ligne de la table de vérité pour laquelle Φ = 1 (par exemple la conjonction associée à la ligne 01101 est ¬x1x2x3 ∧ ¬x4x5 ), puis de prendre la disjonction de ces conjonctions. On peut souvent simplifier le résultat, en regroupant plusieurs lignes de la table de vérité : par exemple si Φ = 1 pour x1 = 0, x3 = 1, et x4 = 0, quelles que soient les valeurs de x2 et x5, on peut regouper quatre conjonctions en une, à savoir ¬x1x3 ∧ ¬x4 ; notons cependant que dans ce cas la forme normale n'est plus unique (différents regroupements sont possibles, qui ne conduisent pas à la même formule, comme on s'en convaincra facilement en appliquant la méthode à la formule xy ), ce qui est gênant pour une forme dite normale…

Une autre façon d'obtenir une forme normale disjonctive (respectivement conjonctive) est d'utiliser les lois de distributivité : en effet l'opérateur ∧ se comporte comme un produit (pour des variables dont les seules valeurs sont 0 et 1), et l'opérateur ∨ comme une somme (sauf que 1 + 1 = 1) ; transformer une formule en forme normale disjonctive est analogue au développement d'un polynôme (il faut appliquer aussi les lois de Morgan lorsque c'est nécessaire), tandis qu'une transformation en forme normale conjonctive est analogue à une factorisation — mais c'est beaucoup plus simple, car par dualité on a la distributivité inhabituelle p + q r = ( p + q ) ( p + r ).

1.2. Egalité

Noter que le signe d'égalité peut être interprété de deux façons (équivalentes) : il signifie d'une part que le terme gauche et le terme droit ont même table de vérité ; d'autre part on peut considérer l'égalité comme un connecteur logique, vrai si et seulement si ses deux arguments sont égaux, autrement dit considérer x = y comme une abréviation de :

(xy) ∨ (¬x ∧ ¬y)

ou encore de :

xy) ∧ (x ∨ ¬y)

On peut écrire la table de vérité pour se convaincre que la seconde formule est la forme normale conjonctive de l'égalité, ou bien se rappeler que ¬xy est l'implication xy (qui est fausse si et seulement si l'hypothèse x est vraie, en même temps que la conclusion y est fausse). L'égalité désigne donc le même connecteur logique que ⇔ ; sa négation est l'inégalité ≠ , notée beaucoup plus souvent xor (ou exclusif, vrai si l'un des arguments et un seul est vrai), et c'est aussi l'addition modulo 2 (ce qui explique l'importance de cet opérateur) !

1.3. Tautologies

Une tautologie est une formule toujours vraie, quelles que soient les valeurs attribuées aux variables x1xn qui la composent ; exemple :

( x1x2 ) ⇔ ( ¬x2 ⇒ ¬x1 )

est une tautologie, qui exprime l'équivalence entre une implication et sa contraposée ; il suffit de remplacer le connecteur ⇒ par sa définition, rappelée ci-dessus, dans chacun de ces deux termes, pour s'en convaincre (il faut réduire aussi une double négation). Autre exemple :

( ( x1x2 ) ∧ ( x2x3 ) ) ⇒ ( x1x3 )

est une tautologie, qui exprime la transitivité de l'implication. En remplaçant le connecteur ⇒ par sa définition, et en appliquant les lois de Morgan, cette tautologie devient :

( x1 ∧ ¬x2 ) ∨ ( x2 ∧ ¬x3 ) ∨ ¬x1x3

Bien que cette formule ne comporte que trois variables, on admettra qu'il ne saute pas aux yeux qu'il s'agit d'une tautologie. Le problème de décision TAUTOLOGIE consiste justement à déterminer si une formule Φ est une tautologie. Il existe un algorithme très simple pour le résoudre, à savoir construire la table de vérité de la formule, et vérifier que pour chacune des 2n lignes de cette table, Φ vaut 1 ; pour les formules dont la taille (c'est-à-dire le nombre de symboles utilisés pour écrire la formule) est bornée par une fonction polynomiale du nombre n de variables, cet algorithme n'est pas polynomial.

En fait on conjecture que TAUTOLOGIE n'appartient même pas à NP : on ne voit pas comment fournir un certificat autre que la table de vérité, or la taille de cette dernière est en général exponentielle par rapport à la taille de la formule. On donnera en fin de chapitre un argument très fort en faveur de cette conjecture.

1.4. SAT

Le problème complémentaire de TAUTOLOGIE est le problème de satisfiabilité, si célèbre qu'on l'appelle par son petit nom, SAT. Une formule Φ est dite satisfiable s'il existe une valeur du vecteur x = x1xn telle que Φ = 1 (on dit que cette valeur de x satisfait Φ). SAT est bien le complémentaire de TAUTOLOGIE, car :

Φ n'est pas une tautologie ⇔ ¬Φ est satisfiable

SAT est clairement dans NP : un certificat est un vecteur x qui satisfait la formule. La section suivante montre qu'il est très peu vraisemblable que SAT soit dans P, car sinon on aurait P = NP.

Signalons qu'il est pourtant très facile de savoir si une formule en forme normale disjonctive est satisfiable : la condition nécessaire et suffisante est que l'une des conjonctions qui la composent soit satisfiable, c'est-à-dire ne comporte pas à la fois une variable et sa négation ; cet algorithme s'exécute en lisant la formule de gauche à droite, et sa complexité est donc linéaire. Pour autant, on ne tient pas là un algorithme polynomial pour résoudre SAT, car la transformation en forme normale disjonctive est analogue au développement d'un polynôme (cf. fin de la section 1.1), et conduit en général à une formule de taille exponentielle par rapport à la taille de la formule initiale (un exemple explicite est fourni en exercice).

Note : bien qu'il n'existe très probablement aucun algorithme polynomial pour résoudre SAT, il existe des méthodes sophistiquées beaucoup moins inefficaces que la recherche d'un vecteur x (satisfaisant la formule) par force brute ; ces méthodes sont importantes pour la démonstration automatique, voir la section "Pour en savoir plus".

2. Réductions

Définition : réduire le problème de décision A au problème de décision B, c'est construire un algorithme f qui transforme toute instance u de A en une instance v = f (u) de B, de telle sorte que :

A ( u ) = B ( f (u ) ) .

Ainsi tout algorithme qui résout B résout A par la même occasion : pour savoir si une instance u vérifie A, on transforme u en v = f (u), et on "interroge" B ; selon que la "réponse" obtenue est "oui" ou "non", la réponse à la question initiale — celle concernant A (u) , est positive ou négative. On verra de nombreux exemples dans la suite de ce chapitre.

Si B est dans P, et si la transformation f est polynomiale, alors A est aussi dans P ; le résultat reste valable en remplaçant P par NP, car un certificat x et un vérifieur polynomial V pour B fournissent un certificat (x lui-même) et un vérifieur polynomial (par composition) pour A :

A (u) = 1 ⇔ B ( f (u) ) = 1 ⇔ ∃x V ( f (u), x ) = 1

Retenons ce résultat (il faut faire attention à l'ordre de A et B dans la conclusion, le mieux est de refaire mentalement le raisonnement ci-dessus lorsqu'on a un doute) :

S'il existe une réduction polynomiale de A en B, alors
BPAP (respectivement BNPANP ) .

Un problème de décision B est dit NP-difficile ( NP-hard chez les anglo-saxons) si tout problème A dans NP peut être réduit polynomialement à B ; si en outre B est lui-même dans NP, on dit que B est NP-complet. Un tel problème est en quelque sorte universel, pour la classe NP, puisqu'un algorithme de résolution de B peut servir ipso facto à résoudre n'importe quel problème de NP ! En particulier si l'on espère prouver P = NP, il suffit de découvrir un algorithme (déterministe) polynomial pour un problème NP-complet (un seul suffit) ; si au contraire PNP, alors aucun problème NP-complet n'appartient à P.

3. SAT est NP-complet

3.1. Théorème de Cook et Levin

On peut se demander si la définition précédente est raisonnable, autrement dit s'il existe des problèmes NP-complets ; la réponse est positive (sinon on n'en parlerait pas), et a été fournie indépendamment par Cook (1971) et Levin (1973), un mathématicien russe qui ne connaissait pas les travaux du précédent, car du temps de l'URSS, les résultats scientifiques circulaient plus lentement qu'aujourd'hui (les déplacements de scientifiques hors d'URSS étaient rarement autorisés, et … Internet n'existait pas) :

Théorème de Cook (et Levin) : SAT est NP-complet.

Prouver ce théorème, à savoir que tout problème de décision dans NP, c'est-à-dire possédant un vérifieur polynomial, peut être réduit à un problème sur des formules booléennes, semble a priori hors de portée. En fait, ce n'est pas très difficile, car un programme informatique est exécuté par du matériel électronique (processeur, mémoire), construit à partir de portes logiques élémentaires. La section suivante examine ce processus de plus près, et donne les idées essentielles de la preuve du théorème de Cook.

3.2. Circuits logiques

Chaque fois qu'une instruction-machine est exécutée, quelques bits (en général un mot-machine, soit 32 ou 64 bits aujourd'hui) de la mémoire vive ou des registres (y compris le compteur ordinal), sont modifiés en fonction de la valeur de quelques autres bits (en général un ou deux mots-machine), par des circuits logiques. L'exécution d'une instruction élémentaire peut donc être décrite par une formule booléenne comportant quelques dizaines de variables : ne pas oublier que l'affectation peut être représentée, comme l'égalité, par une formule booléenne (voir section 1.2). En représentant l'état de la mémoire (y compris les registres), à l'instant t, par une famille de variables booléennes bi t , chacune exprimant la valeur du bit i à l'instant t, on obtient le principe suivant :

L'exécution d'un algorithme de décision A (u), où u désigne un mot de n bits u1un , peut être décrit par une formule booléenne
Φ (u1, …, un , y , b11, …, bi t , … )
satisfiable si et seulement si y = A (u).

Cette formulation suppose l'algorithme déterministe, ce qui implique que les valeurs des variables auxiliaires bi t (qui représentent les états intermédiaires de la mémoire pendant le calcul), dépendent uniquement des ui ; autrement dit il existe une seule affectation de valeurs à ces variables qui satisfait Φ, lorsque y = A (u).

Si l'algorithme n'est pas déterministe, ce qui précède reste vrai pour chaque branche de calcul ; des branches différentes correspondent à des valeurs différentes des bi t , et peuvent conduire à des résultats différents. Il suffit par définition que l'un de ces résultats soit égal 1 pour qu'on ait A (u) = 1 ; donc A (u) = 1 si et seulement si Φ (u, 1, b) est satisfiable (u désigne la suite des ui , qui est donnée; b désigne la suite des variables auxilaires bi t , qu'il faut ajuster pour satisfaire Φ).

La démonstration du théorème de Cook est presque achevée, sauf que toute notion de complexité a, pour l'instant, disparu, ce qui est troublant. Reste à combler cette lacune, en montrant que la réduction ci-dessus de n'importe quel problème A dans NP au problème de satisfiabilité d'une formule Φ (construite à partir de A) est bien polynomiale. Cela résulte de deux faits :

On déduit de ces deux faits que la taille de Φ, quoique gigantesque (programmer uniquement avec des booléens serait plutôt pénible), est bornée par une fonction polynomiale de n. L'algorithme de construction de Φ ne peut être décrit rigoureusement que pour une machine de Turing, mais on se convaincra facilement que sa complexité est du même ordre de grandeur que la taille de Φ, ce qui achève la preuve du théorème de Cook. Pour donner tous les détails, il faut un modèle de calcul précis, usuellement celui des machines de Turing, voir par exemple la section 7.3 de l'ouvrage de Sipser ; l'exercice 2 du devoir 2003 donne de son côté les détails pour le problème SUBSET-SUM ; la première partie de l'exercice 3 de l'examen de janvier 2005 présente une réduction (beaucoup plus facile) de 3-COL (coloration d'un graphe avec 3 couleurs) à SAT.

L'introduction de variables booléennes pour décrire les résultats intermédiaires d'un calcul est aujourd'hui souvent remplacée par une définition formelle des circuits logiques, et par l'étude de leur complexité, voir la section 9.3 de l'ouvrage de Sipser.

3.3. CNF est NP-complet

CNF (conjunctive nomal form) est le problème de décision SAT, restreint aux formules en forme normale conjonctive (conjonctions de clauses) ; malgré cette restriction, il reste NP-complet.

Avant de démontrer ce résultat, il faut éclaircir les relations entre généralisation, restriction, réduction, et la propriété, pour un problème de décision, d'être NP-complet. Le principe fondamental est le suivant :

S'il existe une réduction polynomiale de A en B
(en abrégé AB ), alors
A est NP-complet ⇒ B est NP-complet.

Ce résultat est une simple application de la transitivité des réductions polynomiales : par hypothèse tout problème dans NP peut être réduit en A, et A lui-même peut être réduit en B ; donc tout problème dans NP peut être réduit en B. Note : on hésite souvent sur l'ordre de A et B dans la conclusion, et on confond souvent ce résultat avec celui de la section 2, où l'ordre est inversé ; le mieux est de refaire mentalement, chaque fois, le raisonnement ci-dessus.

Si un problème A (par exemple SAT) est une généralisation d'un problème B (par exemple CNF), A est a priori plus difficile ; inversement B est une restriction de A, et B est a priori plus facile. Quelques instants (indispensables) de réflexion montrent qu'il existe une réduction immédiate de B en A (en abrégé BA ) : à chaque instance de B, il suffit d'associer l'instance plus générale de A, et de résoudre ce dernier problème. Donc si B (le problème restreint) est NP-complet, A (le problème général) l'est aussi.

Par contre, pour prouver que CNF est NP-complet, il faut trouver une réduction SATCNF, ce qui n'est pas évident (autrement dit il faut montrer que satisfaire une formule en forme normale conjonctive est essentiellement aussi difficile que satisfaire une formule booléenne quelconque). Pour cela, il faut transformer (efficacement) toute formule Φ en une formule F, en forme normale conjonctive, telle que :

Φ est satisfiable ⇔ F est satisfiable.

La formule Φ peut être représentée, comme toute expression, par un arbre, dont les feuilles sont les variables, et les noeuds internes des connecteurs logiques. D'abord, en appliquant les lois de Morgan, on peut faire descendre dans l'arbre les négations, jusqu'à ce qu'elles s'appliquent directement aux feuilles. Restent deux cas, où la construction de F est récursive :

Evaluons enfin la complexité de la transformation de Φ en F, en fonction de la taille n de Φ , c'est-à-dire du nombre de noeuds de l'arbre. Lors de la phase initiale (descente des négations), le nombre d'applications des lois de Morgan est au pire égal au nombre de noeuds binaires (conjonctions et disjonctions), qui lui ne change pas — la suppression des doubles négations empêche l'application répétée d'une loi de Morgan au même noeud. Lors du traitement d'une conjonction ou d'une disjonction, le nombre de clauses ne change pas ; on en déduit par récurrence, que le nombre de clauses de F est O (n). Le traitement d'une conjonction est immédiat, son coût est fixe ; le traitement d'une disjonction consiste essentiellement à ajouter une variable (soit y, soit ¬y) à chaque clause, donc son coût est proportionnel au nombre de clauses ; par conséquent la complexité de la transformation globale est O ( n2 ).

Attention : la formule F n'est pas équivalente à Φ (elle comporte des variables supplémentaires). Les algorithmes élémentaires de transformation de formules en forme normale conjonctive (voir section 1.1), ont une complexité exponentielle ; découvrir un algorithme polynomial pour cette tâche démontrerait que P = NP (surprise) ; en effet, un tel algorithme serait facilement adaptable, par dualité, pour transformer une formule en forme normale disjonctive, et le problème DNF (disjunctive normal form) n'est pas du tout difficile (rien à voir, du point de vue de la complexité, avec CNF) : voir section 1.4.

3.4. 3-CNF est NP-complet

3-CNF est souvent appelé 3-SAT ; ce flottement dans la terminologie vient de ce qu'il est facile d'adapter les détails de la démonstration du théorème de Cook, pour obtenir directement une formule en forme normale conjonctive ; certains auteurs confondent donc SAT et CNF.

3-CNF est le problème de décision CNF, restreint au cas où chaque clause comporte au plus trois variables (ou exactement trois, c'est la même chose, car par exemple la clause à deux variables x∨¬y est équivalente à la clause à trois variables xx∨¬y ) ; malgré cette restriction, il reste NP-complet.

La réduction de CNF à 3-CNF est voisine de la réduction de SAT à CNF ; il suffit de transformer toute clause C qui comporte au moins quatre variables, en une conjonction F de clauses à trois variables, de telle sorte que :

C est satisfiable ⇔ F est satisfiable.

Un exemple suffira, soit C = x1∨¬x2x3x4∨¬x5 ; on introduit deux variables supplémentaires y1 , y2 , et on pose :

F = ( x1∨¬x2y1 ) ∧ ( ¬y1x3y2 ) ∧ ( ¬y2x4∨¬x5 )

Supposons que C soit satisfaite, par exemple avec x2 = 0 ; alors la première clause de F est satisfaite, la seconde l'est en choisissant y1 = 0 et la troisième l'est en choisissant y2 = 0 ; si C est satisfaite par le choix x3 = 1, on choisira y1 = 1 pour satisfaire la première clause de F, et y2 = 0 pour satisfaire la troisième ; etc. Inversement, si F est satisfaite, trois cas se présentent :

Ceci achève la réduction de CNF en 3-CNF. Notons que par contre 2-CNF (chaque clause comporte deux variables) est un problème polynomial. Le principe d'un algorithme efficace de résolution de 2-CNF est le suivant : on choisit la variable qui apparaît le plus souvent dans les clauses, disons que c'est x1 ; on étudie alors séparément les deux cas :

Puis on recommence, dans chacun des cas, avec la variable dont la valeur n'est pas encore connue, et qui apparaît le plus fréquemment dans les clauses restantes. L'important est qu'un choix pour x1 détermine la valeur d'autres variables xi , ce qui évite l'explosion exponentielle habituelle (pour le vérifier, il faut une preuve rigoureuse, que nous ne donnerons pas).

4. Problèmes difficiles sur les graphes

Cliques et recouvrements, chemins et circuits hamiltoniens, colorations, isomorphisme de graphes.

4.1. Colorations

Le problème de la coloration d'un graphe est le suivant :

Un théorème célèbre, particulièrement difficile à démontrer, affirme que tout graphe planaire peut être colorié avec 4 couleurs ; un graphe est planaire s'il est possible de le dessiner dans le plan (ou, ce qui revient au même, sur une sphère) sans que deux arêtes distinctes se croisent.

En théorie de la complexité, on a le théorème suivant :

Le problème de la coloration avec 3 couleurs (en abrégé 3-COL)
est NP-complet.

La construction qui permet de réduire CNF à 3-COL fait l'objet de la seconde partie de l'exercice 3 de l'examen de janvier 2005, disponible avec un corrigé.

5. Problèmes difficiles en arithmétique

SUBSET-SUM et sac à dos, factorisation.

5.1. SUBSET-SUM

6. Complémentaires des problèmes NP-complets

Théorème : si NPco-NP, alors le complémentaire d'un problème NP-complet n'est jamais dans NP.

Pour en savoir plus