Le théorème de Cook ou théorème de Cook-Levin est un théorème fondamental de la théorie de la complexité des algorithmes. Il a été démontré en 1971 par Stephen Cook et, sensiblement au même moment, par Leonid Levin.
Il affirme que le problème SAT est NP-complet, permettant ainsi par réduction polynomiale de classer beaucoup d'autres problèmes.
Un problème de décision est dans NP si une machine de Turing non déterministe peut trouver une solution du problème 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 un assignement des variables qui rend l'ensemble de l'expression vrai.
Le problème SAT est dans NP car une machine de Turing non déterministe peut deviner un assignement des variables, déterminer la valeur de l'expression entière et répondre oui ou non à la question de savoir si l'expression complète est vraie ou fausse.
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 état 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 satisfaisable 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 ∈ Σ, and 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) and 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 acceptable. | O(1) |
S'il y a un calcul acceptable pour M pour l'entrée I, alors B est satisfaisable, en assignant Tijk, Hik and 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'assignement des variables.
Quel est la dimension de B ? Il y a O(p(n)²) 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)²). Ainsi la taille de B est O((log p(n)) p(n)²). C'est polynomial en n, la taille de l'entrée, la transformation est donc polynomiale, comme requis.
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 présentent plus de 300 problèmes NP-complets et de nouveaux problèmes sont toujours étudiés pour être classés .