Stephen Arthur Cook

ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Stephen Arthur Cook, américain (et canadien), 1939- » Leonid A. Levin

Né à Buffalo (État de New York), Stephen Cook est issu d'un père chimiste et d'une mère enseignante. Les années 1950 marquent l'avènement du transistor et des premiers ordinateurs. Le jeune Stephen s'intéresse à l'électronique et s'oriente vers l'informatique naissante à l'université du Michigan puis à Harvard où étaient déjà enseignés des cours sur l'intelligence artificielle, les langages informatiques et la théorie de la complexité des algorithmes consistant à étudier et optimiser l'efficacité d'un algorithme en termes de temps de calcul.

Stephen Cook soutient (1966) sa thèse de doctorat intitulée On the minimum computation time of functions. Après 4 ans d'enseignement à Berkeley (univ. Californie), il obtient un poste en informatique à l'université de Toronto (Canada) et publie l'année suivante (1971) un mémoire qui fera sa notoriété, The Complexity of theorem proving procedures (De la complexité des procédures de démonstration de théorèmes), où il définit la NP-completude (évoquée ci-après).

➔ En informatique, on désigne généralement par procédure est une suite d'instructions, exprimées dans un langage de programmation, ne conduisant pas à un résultat numérique. Il s'agit donc d'un algorithme particulier. La suite d'instructions numériques z = b; b = a; a = z échangeant les valeurs des variables a et b est une (petite) procédure consistant à échanger les valeurs de a et b. Pour de tels petits programmes, on parle aussi de routines. Intégrés dans un programme informatique ces procédures et routines sont aussi communément appelés sous-programmes.

Stephen Cook fera toute sa carrière à Toronto. A la suite des travaux d'Alan Turing, Stephen Cook est considéré comme le plus éminent spécialiste en matière de complexité des preuves en logique propositionnelle (algorithmes susceptibles d'établir qu'un énoncé est vrai ou faux). Membre de l'Académie des sciences des États-Unis, de l'Académie des sciences de Göttingen, de la Royal Society et de la Société royale du Canada, il est récipiendaire du prix Turing 1982.

La conjecture P = NP ? :

La conjecture P = NP ? ou problème de Stephen Cook ou encore, en anglais, P versus NP problem, est un sujet d'algorithmique portant sur la stratégie à adopter face à la recherche de la solution de la majorité des problèmes de décision : problème que l'on peut ramener à un énoncé mathématique dont on cherche à savoir s'il est vrai ou faux au moyen d'un algorithme approprié. Les prémisses du sujet apparaissent dès la fin du 19è siècle avec la remise en question de la logique mathématique bousculée par les contradictions apparues avec la mise en place de la théorie des ensembles de Cantor.

La notion d'algorithme : » Alan Turing et le problème de la décision : »

Deux méthodes se présentent :

L'une, qualifié de déterministe fait usage d'un algorithme susceptible de conduire à la solution en un temps polynomial et ce pour exprimer que le nombre d'étapes E conduisant au résultat escompté est fini et que si n désigne le nombre de données mises en jeu, E peut être estimé par un polynôme de la variable n. On parle alors d'un problème de classe P.
L'autre se contente de vérifier la (les) solution(s) présumée(s) : c'est une méthode non déterministe faisant appel cependant à un algorithme de validation de la classe P. On parle alors d'un problème de classe NP, N pour Non déterministe.

Dès les premiers temps de l'ère informatique, accélérée par la seconde guerre mondiale dès le début des années 1940, les informaticiens et mathématiciens, principalement logiciens comme Gödel, se sont penchés sur l'efficacité des algorithmes en estimant "acceptable" un temps de calcul polynomial. C'est le cas des algorithmes de calcul élémentaire (addition, multiplication, comparaison, assignations de variables, etc.). Un algorithme en temps polynomial, par exemple en n², est généralement beaucoup plus rapide qu'un algorithme en temps exponentiel, comme 2ⁿ et n! évoqué ci-dessous (exemple 3), mais évidemment plus lent qu'un algorithme en n (dit linéaire).

➔ Un algorithme peut aussi être gourmand en mémoire (celle de l'ordinateur). Les procédures récursives, extrêmement efficaces, peuvent cependant provoquées des dépassements de capacité de la machine utilisée (voir par exemple la fonction d'Ackermann). C'est une contrainte concrète incontournable dont les informaticiens doivent aussi tenir compte en théorie de la complexité.

L'algorithme du pgcd selon Euclide est de classe P, tout comme ce nombre est-il premier ?
La recherche d'un chemin hamiltonien d'un graphe est de classe NP;
La recherche de la primarité (primalité) ou de la factorisation d'un nombre entier n en produit de facteurs premiers relève de la classe NP : on essaye de lui trouver un diviseur premier en le divisant par tous les entiers inférieurs à sa racine carrée. Tant mieux ! si le problème était reconnu de classe P, on aurait trouvé un algorithme que tout "pirate" pourrait connaître et déjouer ainsi les sécurités informatiques dont le cryptage des données se base sur de "grands" nombres premiers (au moins 200 chiffres). » cryptologie (réf.8-11-12)
Le problème du représentant de commerce (ou du "voyageur" de commerce) : monsieur Dupont dont la boîte siège à S a pour mission de rencontrer trois responsables de succursales sises dans les villes A, B et C. Il prépare son parcours, partant de S et revenant à S en cherchant l'itinéraire le plus court. Existe-t-il un algorithme le résolvant en temps polynomial ? Il y a 3! = 6 parcours distincts correspondant au nombre de permutations des éléments A, B et C. Facile dans ce cas de trouver le chemin optimal. Pour 4 succursales, on a 4! = 24 (factorielle 4) parcours possibles; déjà plus pénible à étudier et s'il y a 10 succursales, on en est à 10! = 3 628 800 chemins à comparer... Monsieur Dupont aimerait programmer une petite routine, genre "appli", pour lui faciliter la tâche. Il s'aperçoit vite de la difficulté. Les calculs lui occuperaient une cinquantaine d'années. Pour rappel, la formule de Stirling fournit asymptotiquement n! ≈ √(2πn) × (n/e)ⁿ avec une erreur en 1/n : ce qui indique n! > 2ⁿ dès que n ≥ 4 : l'accroissement du nombre d'itinéraires possibles est bien plus qu'exponentiel, le temps de calcul pouvant rapidement atteindre l'âge de l'Univers, à savoir environ 13,8 milliards d'années. En effet, ce nombre correspond à 4,4×10¹⁷ secondes, or 19! ≈ 1,2×10¹⁷et 20! ≈ 2,4×10¹⁸. Ainsi, 20! (factorielle 20) secondes surpasse l'âge de l'Univers... Par comparaison, 2²⁰ = 1 048 576 (≃ 1 × 10⁶) et e²⁰ ≃ 485 165 195 (≃ 5 × 10⁸). Quoi qu'il en soit ce problème n'est donc pas de classe P. Tel qu'il est posé (chemin le plus court), c'est actuellement un problème irrésoluble à l'échelle humaine, même assistée par les plus puissants ordinateurs (un des plus complexes qui soient). Cependant :

➔ Face à un problème combinatoire complexe, on peut limiter la complexité en ajoutant des contraintes limitant le nombre d'étapes (au sens de la machine de Turing) dans la recherche de la solution; on est ramené à un problème d'optimisation pouvant encore s'avérer très difficile. Mais on peut rester dans le domaine d'un problème de décision de classe NP : dans le cas du voyageur de commerce, une contrainte pourrait être que la distance soit inférieure ou égale à un certain kilométrage considéré comme "acceptable" et vérifier qu'un chemin "donné" vérifie ou non la contrainte devient alors élémentaire.

L'addition de deux entiers d'au plus n chiffres est linéaire en temps de calcul : elle fait appel à n + n additions élémentaires augmentées d'au plus n retenues : le temps de calcul est donc proportionnel à 3n : c'est un O(n).
Dans le cas de la multiplication de deux entiers d'au plus n chiffres, on effectue n × n multiplications élémentaires de chaque chiffre du multiplicateur par chaque chiffre du multiplicande en procédant à n(n-1) retenues au plus (additions élémentaires), auxquelles s'ajoutent les additions des résultats partiels, au plus n(n+1). Finalement notre multiplication demande au plus 2n² opérations élémentaires. En termes de temps, tout dépend de la vitesse du processeur pour effectuer ces opérations : un ordinateur 2 fois plus rapide mettra grosso modo 2 fois moins de temps, raison pour laquelle on dira que l'algorithme de multiplication est polynomial en n² (et non pas 2n²) : c'est un O(n²).
L'algorithme du tri à bulles est un O(n²).
Le calcul du déterminant d'une matrice carrée n × n est un O(n³). Le calcul de l'inverse également puisque le calcul des mineurs, des divisions et des transpositions sont d'ordre inférieur.
Cette boucle de calcul écrite en JavaScript, calculant la somme des n premiers entiers naturels, est linéaire en temps de calcul :

n = 1000; s = 0; for(k=1;k<=n;k++) {s = s + k}

le temps d'exécution de la boucle est proportionnel à n car l'addition s + k est un O(n) ainsi que l'affectation s = s + k.
Que dire de la complexité algorithmique de ce petit programme de calcul du nombre e, basé sur la formule e = lim (1 + 1/n⁾ⁿ :

n = 10000; e = 1 ; f = 1+1/n; for(k=1; k<=n; k++) {e = e*f}; alert("e = "+e)

L'affectation e = e*f dans la boucle est un O(n²) répété n fois; cet algorithme est donc un O(n³).

∗∗∗
Montrer que l'algorithme d'Euclide pour le calcul du pgcd de deux entiers est en O(n³)

➔ On parle aussi d'algorithme en temps logarithmique, par exemple en logn, donc très rapide a priori (» exemple ci-dessous). Tout comme en analyse mathématique, on utilise la notation grand O de Landau s'exprimant dans le cas de deux fonctions numériques au voisinage de l'infini par :

f = O(g) ⇔ pour x suffisamment grand, il existe un réel M > 0 tel que |f(x)| ≤ M. |g(x)|

Le jeu consistant à rechercher un entier x dans une fourchette [0,n], n entier, admet une solution très efficace en temps logarithmique au moyen d'un algorithme dichotomique : le joueur 1 propose E(n/2), partie entière de n/2; s'il s'agit de x le jeu s'arrête, sinon le joueur 2 répond "plus petit", resp. "plus grand"; le joueur 1 propose alors E(n/4), resp. E(3n/4), etc. L'amplitude de recherche est divisée par 2 à chaque essai. Or, tout entier n est compris entre deux puissances consécutives de 2 : il existe un entier p tel que 2^p ≤ n ≤ 2^p+1; autrement dit, il existe un entier p tel que 1 ≤ n/2^p ≤ 2 : le joueur 1 trouve x à 1 près lorsque p ≤ ln(n)/ln(2) ≤ p + 1. Par exemple si n = 1000, ln(n)/ln(2) = 9,9657 : le joueur trouve x en 10 coups au plus. L'algorithme est un O(ln n).
» Voir aussi la comparaison entre recherche dichotomique et séquentielle ainsi que la résolution dichotomique d'une équation f(x) = 0).

Cook exprime en introduction de sa conjecture :

Le problème consiste à déterminer si un langage adapté à un algorithme non déterministe en temps polynomial (classe NP) l'est également par un algorithme déterministe en temps polynomial (classe P). Pour définir précisément le problème, il est nécessaire de donner un modèle formel d’ordinateur. Le modèle informatique standard en théorie de la calculabilité est la machine de Turing, introduite par Alan Turing en 1936. Bien que le modèle ait été introduit avant la construction d'ordinateurs physiques, il continue néanmoins d'être accepté comme le modèle informatique approprié pour définir la notion de fonction calculable.

La machine de Turing, machine de "papier", peut paraître has been en l'occurrence mais elle a le grand avantage d'être indémodable en tant que référence logique indifférente aux progrès techniques de l'informatique. Comme l'écrit Jean-Yves Girard, spécialiste en logique mathématique (CNRS, univ. Marseille-Luminy, » réf.5) : les machines de Turing sont passées du statut honorable d'une présentation parmi d'autres de la calculabilité à celui bien plus enviable de mètre-étalon de la complexité.

à l'origine, la machine de Turing est, par construction si l'on peut dire, une machine déterministe. Aujourd'hui, en théorie de la complexité, on parle de machine de Turing non déterministe pour exprimer qu'une telle machine peut, à une étape, faire le choix d'une instruction parmi d'autres (de manière aléatoire ou programmée) : en d'autres termes, elle essaye. Le nombre d'essais devant bien sûr être fini.

Dans ce contexte, un problème de décision est de classe P (resp. NP), si une machine de Turing déterministe (resp. non déterministe) est capable de répondre "oui" ou "non" en un temps polynomial.

Par définition, un problème NP apparaît "difficile" et les problèmes de cette classe sont pléthore, raison pour laquelle les spécialistes en algorithmique ont cherché à comparer le niveau théorique de complexité algorithmique des problèmes NP (» réf.6-9).

Le problème SAT :

Étant donné un prédicat, formule propositionnelle F construite sur un ensemble fini de variables logiques au moyen des connecteurs logiques usuels (conjonction ∧, disjonction ∨, négation), on peut fournir à une machine de Turing une assignation des variables afin de savoir si F est alors vraie ou fausse. Plus difficile est le problème NP suivant :

Peut-on exhiber un algorithme universel susceptible de répondre oui ou non à la question
existe-t-il une assignation de ces variables pour laquelle F est vraie.

Ce problème de décision dénommé SAT (satisfiability = satisfiabilité, » réf.10) fut étudié par Cook. On peut l'exprimer plus formellement afin de l'adapter au mode de "raisonnement" d'une machine de Turing non déterministe : Cook montra que tout prédicat F, comme défini ci-dessus, peut se décomposer en un nombre fini C₁ ∧ C₂ ∧ ... ∧ C_n de conjonctions de clauses, dénommant ainsi un nombre fini de disjonctions de prédicats d'une seule variable (par exemple x ∨ y, disjonction de x et de la négation de y). On parle aujourd'hui de forme normale conjonctive.

Voulez-vous jouer au SATgame ? : »
(par Olivier Roussel, centre de recherche en informatique de Lens)

Théorème de Cook-Levin :

Le problème SAT fait partie des problèmes NP les plus étudiés non solutionnés de nos jours (2019) car dans un mémoire intitulé Complexity of theorem proving procedures, publié à Toronto en 1971, Cook parvient à prouver ce résultat fondamental en théorie de la complexité selon lequel :

Tout problème NP peut se réduire au problème SAT par le biais d'un algorithme en temps polynomial
soumis à une machine de Turing déterministe.

Réduire un problème P1 à un problème P2, c'est définir une fonction capable de convertir toute instance de P1 en une instance de P2 (En informatique une instance est un élément particulier d'une classe de données). Si l'algorithme définissant cette fonction est en temps polynomial, la réduction est dite polynomiale. On pourra lire l'article de Stephen Cook en réf.11, les approches de Jean Bétrema (réf.13b) et de Denis Trystram, moins abstraites, sont d'approche plus aisée.

i Leonid Anatolievitch Levin (1948-) : logicien et informaticien ukraino-américain qui étudia à l'université d'État de Moscou (université Lomonosov). En 1972, il présente une première thèse de doctorat sous la direction de Andreï Kolmogorov, intitulée Some Theorems on the Algorithmic Approach to Probability Theory and Information Theory, qui lui sera refusée pour des motifs politiques (à cette époque, l'Ukraine est une des républiques soviétiques de l'URSS alors dirigée par Nikolaï Podgorny, il n'était pas recommandé d'exprimer la moindre critique vis à vis du régime).
Quelques années plus tard, Leonid Levin émigre aux États-Unis et présente (1979) une nouvelle thèse au MIT (Massachussetts Institute of Technology) : Une notion générale d'indépendance des objets mathématiques : ses applications à certains problèmes en théorie des probabilités, logique mathématique et théorie des algorithmes, en lien avec les théorèmes d'incomplétude de Gödel. Professeur à l'université de Boston, Leonid Levin fut élu membre de l'Académie des Sciences des États-Unis en avril 2019.
On pourra consulter son CV à cette adresse : https://www.cs.bu.edu/fac/lnd/research/curv.htm. N.B. Mikhaïl Vasilievich Lomonosov (1711-1765) fut un savant russe, écrivain, astronome et chimiste.

➔ La réduction s'applique également aux problèmes de classe P : si P1 et P2 sont deux problèmes de décision, P2 étant de classe P et P1 se réduisant à P2 par un algorithme en temps polynomial, alors P1 est de classe P.

En termes de complexité, dire que P1 est une réduction de P2 signifie en particulier que P2 est plus "difficile" que P1 car si P2 est résolu, il en sera de même de P1 puisque ce dernier se réduit à P2. Dans ce contexte, certains logiciens et informaticiens notent P1 ≤ P2 ou encore P1 α P2. La relation ainsi définie est en effet une relation d'ordre dans l'ensemble des problèmes de décision.

A la même époque, et indépendamment, le logicien et informaticien russe (plus précisément ukrainien) Leonid Levin est arrivé à la même conclusion en étudiant le problème de la partition, à savoir :

Étant donné un ensemble E d'entiers naturels exhiber un algorithme répondant oui ou non à la question :
E est-il décomposable en la réunion de deux sous-ensembles disjoints de même somme.

Mais ses travaux n'étaient pas connus dans le monde occidental avant 1974. Un exemple trivial d'un tel ensemble peut être donné par E = {1, 2, 5, 6, 8, 10} = {1, 2, 5, 8}∪{6, 10}, partition dont la somme des éléments de chaque partie est 16.

La NP-complétude et P = NP ?:

Le théorème de cook-Levin a fait grandement avancer les recherches sur la complexité algorithmique. Suite à ce résultat, les spécialistes du sujet ont qualifié de complet tout problème vérifiant ce théorème. Ainsi :

Un problème de décision de classe NP est qualifié de NP-complet (» réf.13) si tout problème NP peut être réduit à ce dernier en temps polynomial par une machine de Turing déterministe.

De tels problèmes sont donc difficiles. Un très grand nombre de problèmes NP-complets ont depuis été listés dans tous les domaines, économique en particulier. Mais depuis 50 ans, aucun algorithme de résolution n'a pu être découvert pour ces problèmes. La classe des algorithmes de type P étant incluse dans celle de type NP, la conjecture P = NP ? est équivalente à NP ⊂ P. La NP-complétude permet d'affirmer que si un seul des problèmes NP-complets était résolu, s'avérant de classe P, par exemple le problème SAT, alors l'égalité P = NP serait prouvée.

Pour conclure cette brève introduction :

La conjecture P = NP fait partie des 7 problèmes à 1 million de dollars (Millenium prize problems) du Clay Mathematics Institute mis en jeu en mai 2000. Voyez l'article (ardu et en anglais) de Stephen Cook sur le site de l'Institut (» réf.11c). L'existence de la classe NP n'est peut-être que l'expression de notre insuffisance en matière d'algorithmique face à des problèmes trop complexes. Le problème se pose depuis environ 70 ans; c'est peu. Il a fallu attendre près de 4000 ans pour savoir que π est un nombre transcendant...

Mais les spécialistes en algorithmique, mathématiciens informaticiens, penchent très majoritairement vers P ≠ NP et pensent fortement probable que démontrer P = NP soit indécidable dans le système ZFC de la théorie des ensembles, fondement de la logique mathématique, tout comme, par exemple, l'hypothèse du continu. Mais les recherches se poursuivent; déclarer indécidable un problème de décision est une forme de renoncement peu en usage dans le monde mathématique. D'autant que le problème est crucial au regard de l'omniprésence de l'informatique tant dans notre quotidien que dans le développement de la robotique et de l'intelligence artificielle dans des domaines aussi variés que l'industrie, les communications, l'économie, la médecine, la sécurité militaire ou bancaire. Heureusement, dans tous ces domaines, les chercheurs ont su généralement développer des algorithmes de résolution approchée et si NP s'avère P, nul doute que le génie humain trouvera les algorithmes convoités.

Les références ci-dessous aideront le lecteur intéressé à approfondir ce difficile et passionnant sujet à la frontière entre mathématiques, théorie des langages, informatique théorique et philosophie des sciences.

» Turing , Smale , Gödel

➔ Pour en savoir plus :

a) Biographie de Stephen Cook sur le site du prix Turing :
http://amturing.acm.org/award_winners/cook_n991950.cfm
b) Home page de Stephen A. Cook contenant diverses publications : https://www.cs.toronto.edu/~sacook/
The Millenium prize problèms (les 7 problèmes sont énoncés et commentés par d'éminents spécialistes) :
https://lsk.pe.kr/attachment/491fd21130088EG.pdf
Maths, 7 énigmes à 1 000 000 $ dans la revue Science & Vie, n°995, août 2000.
Les Énigmes Mathématiques du 3e millénaire par Keith Devlin, traduction de Céline Laroche.
Éd. Poche, Le Pommier - 2002.
La machine de Turing , théorie des nombres calculables, fonctions récursives, Alan Turing (traduit de l'anglais).
Commentaires et compléments de J. Y. Girard, Coll. Points Sciences, Ed. du Seuil.
Classes de complexité par Jean Bétréma (LaBRI, CNRS) : https://www.labri.fr/perso/betrema/MC/MC8.html
Complexité et décidabilité, (classes P, NP, NP complétude), cours et exercices de Nhan Le Tanh (univ. Nice) :
http://www.i3s.unice.fr/~nlt/cours/licence/it/s6_itdut_poly.pdf
Complexité et décidabilité, cours d'Alain Lecomte, univ. Paris VIII/Grenoble :
http://lecomte.al.free.fr/ressources/LIC_MIASS/coursTuring.pdf
Introduction à la complexité et à la résolution de problèmes difficiles (problèmes P, NP, NP-complet) :
http://datamove.imag.fr/denis.trystram/SupportsDeCours/Complexite.pdf
Le problème SAT et ses variantes, par Denis Trystram (univ. Grenoble) :
http://datamove.imag.fr/denis.trystram/SupportsDeCours/SATvariations.pdf » voir aussi réf.13a
The Complexity of theorem proving procedures, par Stephen Cook (Toronto, 1971) :
a) version originale numérisée (machine à écrire) : https://www.cs.toronto.edu/~sacook/homepage/1971.pdf
b) Translittération Tex, format pdf par Tim Rohlfs : http://4mhz.de/cook.html
c) The P versus NP problem, par Stephen Cook : http://www.claymath.org/sites/default/files/pvsnp.pdf
The status of the P versus NP problem, par Lance Fortnow (actuellement Illinois Institute of technology, sept. 2009) :
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.227.3908&rep=rep1&type=pdf
ou bien : http://people.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf
a) Problèmes NP-complets, par Jean Bétréma (LaBRI, CNRS) : https://www.labri.fr/perso/betrema/MC/MC9.html
b) NP-complétude par Jean-Michel Dischler (univ. Louis Pasteur, Strabourg) :
http://website2k3.free.fr/cours/aa/NP-compl%E9tude%20(13).pdf
On pourra consulter le cours d'algorithmique avancé de ce professeur à l'adresse :
http://website2k3.free.fr/cours/aa/cours_aa.htm
c) Algorithmique avancée, par Denis Trystram (univ. Grenoble) :
http://datamove.imag.fr/denis.trystram/SupportsDeCours/Complexite.pdf
P = NP, un problème à 1 million de dollars, par Jean-Paul Delahaye sur Interstices.info
Problème P = NP ? sur Wikipedia :
a) https://fr.wikipedia.org/wiki/Problème_P_=_NP
b) https://fr.wikipedia.org/wiki/Problème_NP-complet

Bourbaki

Bombieri