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) ...
ouMparcourt toutes les machines de Turing de´ terministes ` (multi-bande ou pas)
e´2()
Hf={(M,x)|Macceptexapr`esauplusf(|x|)pas}
Soitf finissons le langageune fonction de complexite´ . De´
2)
Th´`eme eor Hf∈DTIME(f(n)3)
Id´eedelapreuve Construire une machine de Turing de´ terministe universelleUfqui simuleM mentaire,, avec “truc” supple´ lasonette d’alarmelpna´tee(mi comme un mot sur un ruban), qui fait rejeter automatiquement chaque motx parqui n’est pas accepte´Men tempsf(|x|). La machineU 1construit la sonette d’alarmeuf(|x|)pourxsur un ruban en temps O(f(|x|)), 2simule chaque pas du travail deMen tempsO(f(|x|)2), 3accepte ou rejette le motx(s’il le faut) en tempsO(f(|x|)3).
Preuve par diagonalisation Supposonsqu’ilexisteunemachinedeTuringd´eterministeMfqui d´ecideHfen tempsf(bn2c). Construisons une machine de Turing d´eterministediagonalisanteDf, dont le programme sera
Th ´ ` eoreme Hf∈DTIME(f(bn2c))
Dfutilise le motMautant de fois que la machineMfsur le mot (M,M), i.e.,f(b(2n+1)2c) =f(n). . . .