espace nécessaire : plus concrètement, si A utilise un espace g(n) ? f (n), alors B utilise un espace au plus dg(n) pour une constante d. Supposons que L soit décidé par une machine de Turing A en espace g(n) avec g(n) = o(f (n)) Il doit exister un entier n 0 tel que pour n ? n 0 , on ait dg(n) < f (n) Par conséquent, la simulation par B de A sera biencompì ete sur une entrée de longueur n 0 ou plus. Considérons ce qui se passe lorsque B est lancé sur l'entrée A10 n0 . Puisque cette entrée est de taille plus grande que n 0 , B répond l'inverse de la machine A sur la même entrée ,
La machine est sur l'´ etat initial d'un calcul sur le mot abaab, p.82 ,
exemple 7.3 vue comme une machinèmachinè a 2-piles ,
Si l'on peut résoudre leprobì eme B, alors on peut résoudre leprobì eme A. Le probì eme A est donc plus facile que leprobì eme B, noté A ? m B, p.119 ,
Si l'on peut résoudre leprobì eme B en temps polynomial, alors on peut résoudre leprobì eme A en temps polynomial. Leprobì eme A est donc plus facile que leprobì eme, p.153 ,
1) × p(n) codant le diagramme espace-temps du calcul de V sur w, pp.2-160 ,
182 INDEX Bibliographie, 2005. ,
Computational Complexity : A Modern Approach, 2009. ,
DOI : 10.1017/CBO9780511804090
Logique mathématique . Volume I, 1993. ,
Logique Mathématique , volume II, 1993. ,
Logique et théorie des ensembles, 2006. ,
Les démonstrations et les algorithmes, 2008. ,
Computers and Intractability, 1979. ,
Introduction to Automata Theory, Languages, and Computation, 2001. ,
Computability and Complexity from a Programming Perspective, 1997. ,
DOI : 10.1007/978-94-010-0413-8_4
Algorithm design, 2005. ,
Automata and computability, 1997. ,
Logic and complexity, 2004. ,
DOI : 10.1007/978-0-85729-392-3
Enumerable sets are diophantine, Doklady Akademii Nauk SSSR, vol.191, issue.2, pp.279-282, 1970. ,
Introduction to mathematical logic, 1997. ,
DOI : 10.1007/978-1-4615-7288-6
Logic for applications, 1997. ,
Computational Complexity, 1994. ,
Les petits cailloux : Une approche modèlethéorique de l'Algorithmie, 1995. ,
Introductionàtion`tionà l'analyse d'algorithmes, 1996. ,
Introduction to the Theory of Computation, ACM SIGACT News, vol.27, issue.1, 1997. ,
DOI : 10.1145/230514.571645
Fondements mathématiques de l'informatique. Ediscience International, 1994. ,
IntroductionàIntroduction`Introductionà la calculabilité : cours et exercices corrigés, 2001. ,