Théorème de Cook
En informatique théorique, plus précisément en théorie de la complexité, le théorème de Cook aussi appelé théorème de Cook-Levin est le théorème qui affirme que le problème SAT, c'est-à-dire le problème de satisfaisabilité d'une formule de la logique propositionnelle, est NP-complet. Il a été démontré en 1971 par Stephen Cook[1] et, sensiblement au même moment, par Leonid Levin[2].
Ce résultat est important car si on montre qu'il existe un algorithme en temps polynomial pour le problème SAT, alors le problème P = NP est résolu. Par ailleurs, ce résultat permet de montrer la NP-dureté de beaucoup d'autres problèmes, par réduction polynomiale.
Définitions
Un problème de décision est dans NP si une machine de Turing non déterministe le décide en un temps polynomial.
Un problème de décision est NP-complet s'il est dans NP et si tout problème de NP peut se réduire à par une réduction polynomiale.
Une instance de SAT est une expression booléenne qui combine des variables booléennes avec des opérateurs booléens. Une expression est satisfaisable s'il existe une affectation des variables qui rend l'ensemble de l'expression vraie.
Idée de la démonstration
Le problème SAT est dans NP car la machine de Turing non déterministe suivante le décide en temps polynomial :
- Lire l'expression booléenne φ ;
- Pour toute variable p apparaissant dans φ, choisir de manière non déterministe une valeur v(p) dans {0, 1} ;
- Accepter si la valuation v satisfait φ ; refuser sinon.
Pour montrer que le problème SAT est NP-dur, on considère un problème A dans NP. Il existe donc une machine de Turing non déterministe M qui le décide en temps polynomial : pour toute instance x de A, x est une instance positive de A si et seulement s'il existe une exécution acceptante de M avec x sur le ruban d'entrée de longueur polynomiale en |x|. L'idée est donc de construire effectivement en temps polynomial une formule booléenne φ(x) qui dit intuivement « il existe une exécution acceptante de M avec x sur le ruban d'entrée de longueur polynomiale en |x| ». Ainsi, x est une instance positive de A si et seulement si φ(x) est satisfiable. Ainsi, on a une réduction polynomiale de A dans SAT : SAT est donc NP-dur.
Démonstration
Le problème SAT est dans NP.
Supposons maintenant qu'un problème dans NP est résolu par une machine de Turing non déterministe M = (Q, Σ, s, F, δ) (avec Q l'ensemble des états, Σ l'alphabet de symbole de la bande, s ∈ Q l'état initial, F ⊆ Q l'ensemble des états finaux et δ ⊆ ((Q × Σ) × (Q × Σ × {−1,+1})) l'ensemble des transitions) et tel que M accepte ou rejette une instance du problème en temps p(n) où n est la taille de l'instance et p une fonction polynomiale.
Pour chaque instance I, soit une expression booléenne qui est satisfaite si et seulement si la machine M accepte I.
L'expression booléenne est composée de variables extraites de la table suivante, où q ∈ Q, −p(n) ≤ i ≤ p(n), j ∈ Σ et 0 ≤ k ≤ p(n) :
| Variables | Interprétation | Combien ? |
|---|---|---|
| Tijk | Vrai si la case i de la bande contient le symbole j à l'étape k du calcul. | O(p(n)²) |
| Hik | Vrai si la tête de lecture/écriture de M est à la case i de la bande à l'étape k du calcul. | O(p(n)²) |
| Qqk | Vrai si M est dans l'état q à l'étape k du calcul. | O(p(n)) |
Définissons l'expression booléenne B comme la conjonction de clauses de la table suivante, pour tout −p(n) ≤ i ≤ p(n) et 0 ≤ k ≤ p(n) :
| Clauses | Conditions | Interprétation | Combien ? |
|---|---|---|---|
| Tij0 | La cellule i de l'entrée I contient le symbole j. | Contenu initial de la bande. | O(p(n)) |
| Qs0 | Contenu initial de M | O(1) | |
| H00 | Position initiale de la tête de lecture/écriture. | O(1) | |
| Tijk → ¬ Tij′k | j ≠ j′ | Un symbole par case. | O(p(n)²) |
| Tijk = Tij(k+1) ∨ Hik | La bande reste inchangée tant qu'elle n'a pas été écrite. | O(p(n)²) | |
| Qqk → ¬ Qq′k | q ≠ q′ | Un état à la fois seulement. | O(p(n)) |
| Hik → ¬ Hi′k | i ≠ i′ | Une position de la tête sur la bande à la fois. | O(p(n)³) |
| La disjonction des clauses (Hik ∧ Qqk ∧ Tiσk) → (H(i+d)(k+1) ∧ Qq′(k+1) ∧ Tiσ′(k+1)) |
(q, σ, q′, σ′, d) ∈ δ | Transitions possibles à l'étape k quand la tête est en position i. | O(p(n)²) |
| Disjonction des clauses Qf(p(n)) |
f ∈ F. | Doit finir dans un état acceptant. | O(1) |
S'il y a un calcul acceptable pour M pour l'entrée I, alors B est satisfaisable, en assignant Tijk, Hik et Qik leurs interprétations. D'un autre côté, si B est satisfaisable, alors il y a un calcul acceptable pour M avec l'entrée I qui suit les étapes indiquées par l'affectation des variables.
Il y a O(p(n)2) variables booléennes, chacune d'entre elles pouvant être codée en taille O(log p(n)). Le nombre de clauses est O(p(n)3). Ainsi la taille de B est O((log p(n)) p(n)3). C'est polynomial en n, la taille de l'entrée ; la transformation est donc polynomiale, comme requis.
Conséquences
La preuve montre que chaque problème dans NP peut-être réduit en temps polynomial (en fait, LOGSPACE suffit) à une instance de SAT. Ceci montre que si SAT peut-être résolu en temps polynomial par une machine de Turing (déterministe cette fois), alors tous les problèmes dans NP pourront être résolus en temps polynomial. Ainsi la classe de complexité serait égale à la complexité de P.
Le théorème de Cook est la première preuve de NP-complétude. Les autres preuves de NP-complétude se font généralement par réduction polynomiale d'un problème déjà classé comme NP-complet. Par exemple, on peut prouver que le problème 3-SAT (le problème SAT où chaque clause est composé d'au plus trois variables (ou leur négation) en forme normale conjonctive) est NP-complet en exhibant une réduction de SAT vers une instance équivalente de 3-SAT.
Garey et Johnson[3] présentent plus de 300 problèmes NP-complets et de nouveaux problèmes sont toujours étudiés pour être classés.
Références
- (en) Stephen Cook, The complexity of theorem proving procedures, Proceedings of the third annual ACM symposium on Theory of computing (1971), pages 151–158.
- (en) Leonid Levin, « Universal search problems (russe : Универсальные задачи перебора, Universal'nye perebornye zadachi) », Problems of Information Transmission (russe : Проблемы передачи информации, Problemy Peredachi Informatsii), vol. 9, no 3, , p. 115–116 [PDF] (ru), traduit en anglais par (en) B. A. Trakhtenbrot, « A survey of Russian approaches to perebor (brute-force searches) algorithms », Annals of the History of Computing, vol. 6, no 4, , p. 384–400 (DOI 10.1109/MAHC.1984.10036).
- (en) Michael Garey et David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979 (ISBN 0-7167-1045-5).