Réduction en espace logarithmique

La machine de Turing utilisée pour une réduction en espace logarithmique est constituée de trois rubans au lieu d'un : un ruban d'entrée (en lecture seule), un ruban de travail (de taille logarithmique en la taille du ruban d'entrée), et un ruban de sortie (en écriture seule et tel que la tête d'écriture ne peut écrire deux fois sur une même case). Conceptuellement, une réduction en espace logarithmique est une réduction ne nécessitant qu'un nombre constant de pointeurs sur l'entrée.

Le nombre de configurations possibles de la machine de turing en espace logarithmique est polynomialement bornée par la taille de l'entrée, par conséquent, une réduction en espace logarithmique est aussi une réduction en temps polynomial. La réciproque est probablement fausse; en effet, tout langage non trivial de P se réduit en temps polynomial à tout autre langage non trivial de P; cependant, L et NL sont inclus dans P, et une réduction en espace logarithmique d'un langage NL-complet à un langage de L impliquerait NL = L.

À ce jour, L = NL est une question ouverte. De même, nous ne savons pas si l'utilisation de réduction en espace logarithmique (au lieu de réduction en temps polynomial) définit le même ensemble de problèmes NP-complets.

S'il existe des notions de réduction plus faibles encore que les réductions en espace logarithmique, elles sont peu utilisées en pratique car les classes de complexité incluses dans L sont peu étudiées.

• Sanjeev Arora et Boaz Barak, Computational complexity. A modern approach, Cambridge University Press, 2009, 579 p. (ISBN 978-0-521-42426-4, zbMATH 1193.68112, lire en ligne)

• (en) Christos Papadimitriou, Computational Complexity, Reading (Mass), Addison Wesley, 1994, 1^re éd., 159–180 p. (ISBN 0-201-53082-1, zbMATH 0833.68049), « Chapter 8: Reductions And Completeness »

• Portail de l'informatique théorique