Théorème de Cook

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^[1] 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.

Définitions

Article détaillé : Théorie de la complexité des algorithmes.

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 une affectation des variables qui rend l'ensemble de l'expression vrai.

Preuve

Le problème SAT est dans NP car une machine de Turing non déterministe peut deviner une affectation 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 × Σ $\rightarrow$ 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 T_ijk, H_ik and Q_ik 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.

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.

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^[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

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 (en), Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979, ISBN 0-7167-1045-5

• (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)