Machines de Turing et complexité algorithmique

Olivier Hudry*, ENST et CERMSEM

Résumé. L'objectif de cet article consiste à esquisser le rôle des machines de Turing en théorie de la complexité (des algorithmes et des problèmes), dans le domaine de l'optimisation combinatoire. Après avoir rapidement rappelé le contexte historique dans lequel sont nées puis ont évolué les machines de Turing, nous détaillons le fonctionnement de celles-ci, en distinguant entre machines de Turing déterministes et machines de Turing non déterministes. Nous montrons ensuite comment les utiliser pour définir la complexité (en temps de calcul) des algorithmes. Enfin, nous décrivons grâce à elles plusieurs classes fondamentales en théorie de la complexité : la classe P, la classe NP, la classe des problèmes NP-complets et la classe co-NP.
Mots clés : Machines de Turing, théorie de la complexité algorithmique, optimisation combinatoire, calculabilité, classe P, classe NP, problèmes NP-complets, classe co-NP.

Abstract. The aim of this paper is to outline the role of the Turing machines in the field of (algorithms and problems) complexity for combinatorial optimization. After a brief recall of the historic context in which the Turing machines are born and have then evolved, we detail their functioning, both for deterministic and nondeterministic Turing machines. Then we show how to use them in order to define the (time) complexity of algorithms. Last, we depict several fundamental classes of the theory of complexity : P, NP, the class of NP-complete problems and co-NP.
Keywords : Turing machines, theory of algorithmic complexity, combinatorial optimization, calculability, classP, class NP, NP-complete problems, class co-NP.

AMS Classification : 03D10, 03D15, 68Q05, 68Q15, 68Q17.

*Ecole Nationale Supérieure des Télécommunications, 46 rue Barrault, 75634 Paris cedex 13.