Calculabilité et complexité Cours no2

De
Publié par

Calculabilite´ et complexite´oCours n 2Nicolas (Miki) Hermann´LIX, Ecole Polytechniquehermann@lix.polytechnique.fr´ ´Miki Hermann Calculabilite et complexite (2)Hier´ archie des classes de complexite´Soit f une fonction de complexite.´ Definissons´ le langageH = {(M,x)| M accepte x apres` au plus f(|x|) pas}fou` M parcourt toutes les machines de Turing deter´ ministes(multi bande ou pas)´ ´Miki Hermann Calculabilite et complexite (2)Hier´ archie des classes de complexite´Theor´ eme`3H ∈ DTIME(f(n) )fIdee´ de la preuveConstruire une machine de Turing deter´ ministe universelle U quifsimule M, avec “truc” supplementaire´ , la sonette d’alarme (implantee´comme un mot sur un ruban), qui fait rejeter automatiquementchaque mot x qui n’est pas accepte´ par M en temps f(|x|). Lamachine Uf(|x|)1 construit la sonette d’alarmeu pour x sur un ruban en tempsO(f(|x|)),22 simule chaque pas du travail de M en temps O(f(|x|) ),33 accepte ou rejette le mot x (s’il le faut) en temps O(f(|x|) ).´ ´Miki Hermann Calculabilite et complexite (2)Hier´ archie des classes de complexite´Theor´ eme`H ∈/ DTIME(f(bn/2c))fPreuve par diagonalisation´Supposons qu’il existe une machine de Turing deterministe M quif´decide H en temps f(bn/2c). Construisons une machine de Turingf´deterministe diagonalisante D , dont le programme serafD (M) = if M (M,M)== YES then NO else YES fif fD utilise le mot M autant de fois que la machine M sur le motf f(M,M), i.e., f(b(2n+1)/2c)= f(n) ...
Publié le : samedi 24 septembre 2011
Lecture(s) : 31
Nombre de pages : 29
Voir plus Voir moins
Calculabilit´eetcomplexite´ Cours no2
Nicolas (Miki) Hermann
´ LIX, Ecole Polytechnique
hermann@lix.polytechnique.fr
iMikHeramnnaCcllubaliti´eteocpmelixt´e(2)