Complexité P v s NP Un problème qui peut rapporter des millions

Niveau: Supérieur, Master
Complexité : P v.s. NP ? Un problème qui peut rapporter des millions par Olivier Ruatta Université de Limoges - XLIM Email : Résumé Ce cours est la deuxième partie du module « Calculabilité, complexité et évaluation de performances » de la première année du Master Cryptis. Dans la première partie du cours, on a répondu aux questions « Qu'est-ce-que calculer avec une machine de calcul ? » et « Peut-on tout calculer ? ». On ne s'intéresse plus maintenant qu'à des problèmes qu'on sait décidable. On se demande si tout les problèmes présentent le même ordre de difficulté cal- culatoire. 1 Introduction Dans ce document, j'utiliserai librement les notions vues dans la première partie du cours, comme celles relatives aux machines de Turing. Une bonne partie de ce qui sera vue dans cette partie est tiré du livre « Algorithmes et complexité » de H. S. Wilf (publié chez Masson). On décrira quelques problèmes, qui sont souvant des problèmes de décision et des algorithmes. Pour commencer à pouvoir parler de complexité, nous aurons besoin de savoir donner une estimation de celle-ci. Que mesure la complexité ? Ici, nous ne nous intéresserons qu'à la com- plexité en temps, i.e. aux estimations du nombre d'opérations élémentaires effectuées pour sortir d'un algorithme ou pour faire tourner une machine.

• machine de turing


• instance


• relatives aux machines de turing


• temps polynômiale


• classe np


• problème de décision