Cours sur la complexité

Emmanuel Jeandel´COMPLEXITE2`TABLE DES MATIERES1 Machines de Turing 11.1 Machine de Turing classique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Variantes du modele` . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3 Representation´ des donnees´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Complexite´ en temps et en espace 92.1 Definitions´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2 Theor´ emes` de hierarchie´ - Premieres` relations . . . . . . . . . . . . . . . . . . . . . 112.3 Theor´ emes` de hi´ - Diagonalisation . . . . . . . . . . . . . . . . . . . . . . . 122.3.1 Espace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.3.2 Temps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 Non determinisme´ 193.1 Definitions´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2 Premieres` propriet´ es´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.3 Liens avec les classes deterministes´ . . . . . . . . . . . . . . . . . . . . . . . . . . 214 Classes de complexite´ 23´5 Quelques consequences deP =NP 255.1 Factorisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255.2 Certificats polynomiaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265.3 Cryptographie - Fonction One-Way . . . . . . ...