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.
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.
↑(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 (DOI10.1109/MAHC.1984.10036).
