Théorème de Cook

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique théorique, 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é. Il a été démontré en 1971 par Stephen Cook[1] et, sensiblement au même moment, par Leonid Levin [réf. nécessaire].

Il affirme que le problème SAT, c'est-à-dire le problème de satisfiabilité d'une formule de la logique propositionnelle est NP-complet. Ce résultat permet ainsi de classer beaucoup d'autres problèmes, par réduction polynomiale.

Définitions[modifier | modifier le code]

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[modifier | modifier le code]

Le problème SAT est dans NP car la machine de Turing non-déterministe suivante le décide en temps polynomial :

  1. Lire l'expression booléenne φ
  2. Pour toute variable p apparaissant dans φ, choisir de manière non-déterministe une valeur v(p) dans {0, 1}
  3. 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. Et SAT est donc NP-dur.

Démonstration[modifier | modifier le code]

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, sQ l'état initial, FQ 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ù qQ, −p(n) ≤ ip(n), jΣ et 0 ≤ kp(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) ≤ ip(n) et 0 ≤ kp(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 jj′ 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 qq′ Un état à la fois seulement. O(p(n))
Hik → ¬ Hi′k ii′ Une position de la tête sur la bande à la fois. O(p(n)³)
La disjonction des clauses
(HikQqkTiσ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))
fF. 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)2). Ainsi la taille de B est O((log p(n)) p(n)2). C'est polynomial en n, la taille de l'entrée ; la transformation est donc polynomiale, comme requis.

Conséquences[modifier | modifier le code]

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[2] 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[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Cook–Levin theorem » (voir la liste des auteurs).

  1. (en) Stephen Cook, The complexity of theorem proving procedures, Proceedings of the third annual ACM symposium on Theory of computing (1971) pages 151–158
  2. (en) Michael Garey (en) et David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979 (ISBN 0-7167-1045-5).