L. Construction and S. Dans, 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

.. Machine-de-turing, La machine est sur l'´ etat initial d'un calcul sur le mot abaab, p.82

.. La-machine-de-turing-de-l, exemple 7.3 vue comme une machinèmachinè a 2-piles

R. Duprobì-eme-a-vers-leprobì-eme and B. , 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

R. Duprobì-eme-a-vers-leprobì-eme, B. B. Noté, and A. , 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

U. Un-tableau, 1) × p(n) codant le diagramme espace-temps du calcul de V sur w, pp.2-160

.. Inclusions-entre-les-classes-de-complexité, G. Arnold, A. Arnold, and I. Guessarian, 182 INDEX Bibliographie, 2005.

B. Arora, S. Arora, and B. Barak, Computational Complexity : A Modern Approach, 2009.
DOI : 10.1017/CBO9780511804090

. Cori, . Lascar, R. Cori, and D. Lascar, Logique mathématique . Volume I, 1993.

. Cori, . Lascar, R. Cori, and D. Lascar, Logique Mathématique , volume II, 1993.

P. Dehornoy, Logique et théorie des ensembles, 2006.

G. Dowek, Les démonstrations et les algorithmes, 2008.

J. Garey, M. R. Garey, and D. S. Johnson, Computers and Intractability, 1979.

. Hopcroft, Introduction to Automata Theory, Languages, and Computation, 2001.

N. Jones, Computability and Complexity from a Programming Perspective, 1997.
DOI : 10.1007/978-94-010-0413-8_4

. Kleinberg, . Tardos, J. Kleinberg, and E. Tardos, Algorithm design, 2005.

D. Kozen, Automata and computability, 1997.

. Lassaigne, R. De-rougemont-lassaigne, and M. De-rougemont, Logic and complexity, 2004.
DOI : 10.1007/978-0-85729-392-3

Y. Matiyasevich, Enumerable sets are diophantine, Doklady Akademii Nauk SSSR, vol.191, issue.2, pp.279-282, 1970.

E. Mendelson, Introduction to mathematical logic, 1997.
DOI : 10.1007/978-1-4615-7288-6

S. Nerode, A. Nerode, and R. Shore, Logic for applications, 1997.

C. H. Papadimitriou, Computational Complexity, 1994.

B. Poizat, Les petits cailloux : Une approche modèlethéorique de l'Algorithmie, 1995.

F. Sedgewick, R. Sedgewick, and P. Flajolet, Introductionàtion`tionà l'analyse d'algorithmes, 1996.

M. Sipser, Introduction to the Theory of Computation, ACM SIGACT News, vol.27, issue.1, 1997.
DOI : 10.1145/230514.571645

J. Stern, Fondements mathématiques de l'informatique. Ediscience International, 1994.

P. Wolper, IntroductionàIntroduction`Introductionà la calculabilité : cours et exercices corrigés, 2001.