Turing reductionIn computability theory, a Turing reduction from a decision problem to a decision problem is an oracle machine which decides problem given an oracle for (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve if it had available to it a subroutine for solving . The concept can be analogously applied to function problems. If a Turing reduction from to exists, then every algorithm for can be used to produce an algorithm for , by inserting the algorithm for at each place where the oracle machine computing queries the oracle for .
Réduction polynomialeUne réduction polynomiale est un outil d'informatique théorique, plus particulièrement de théorie de la complexité. C'est une classe particulière de réductions particulièrement importante, notamment pour le problème P = NP. Dans le cadre des langages formels pour les problèmes de décision, on dit qu'un langage est réductible en temps polynomial à un langage (noté ) s'il existe une fonction calculable en temps polynomial telle que pour tout , si et seulement si .
Degré de TuringEn informatique et en logique mathématique, le degré de Turing (nommé d'après Alan Turing) ou le degré d'insolubilité d'un ensemble d'entiers naturels mesure le niveau d'insolubilité algorithmique de l'ensemble. Le concept de degré de Turing est fondamental dans la théorie de la calculabilité, où des ensembles d'entiers naturels sont souvent considérés comme des problèmes de décision. Le degré de Turing d'un ensemble révèle combien il est difficile de résoudre le problème de décision associé à cet ensemble, à savoir, déterminer si un nombre arbitraire est dans l'ensemble donné.
Computable functionComputable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output. Computable functions are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines.
Problème NP-completEn théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes : il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette propriété est notée NP ; tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de l
Problème de décisionEn informatique théorique, un problème de décision est une question mathématique dont la réponse est soit « oui », soit « non ». Les logiciens s'y sont intéressés à cause de l'existence ou de la non-existence d'un algorithme répondant à la question posée. Les problèmes de décision interviennent dans deux domaines de la logique : la théorie de la calculabilité et la théorie de la complexité. Parmi les problèmes de décision citons par exemple le problème de l'arrêt, le problème de correspondance de Post ou le dernier théorème de Fermat.
Réduction en espace logarithmiqueEn théorie de la complexité, une réduction en espace logarithmique est une réduction calculable par une machine de Turing disposant d'un espace de travail 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).
Réduction (complexité)En calculabilité et en théorie de la complexité, une réduction est un algorithme transformant une instance d'un problème algorithmique en une ou plusieurs instances d'un autre problème. S'il existe une telle réduction d'un problème A à un problème B, on dit que le problème A se réduit au problème B. Dans ce cas, le problème B est plus difficile que le problème A, puisque l'on peut résoudre le problème A en appliquant la réduction puis un algorithme pour le problème B. On écrit alors A ≤ B.
Problème de l'arrêtvignette|L'animation illustre une machine impossible : il n'y a pas de machine qui lit n'importe quel code source d'un programme et dit si son exécution termine ou non. En théorie de la calculabilité, le problème de l'arrêt est le problème de décision qui détermine, à partir d'une description d'un programme informatique, et d'une entrée, si le programme s'arrête avec cette entrée ou non.
Simple setIn computability theory, a subset of the natural numbers is called simple if it is computably enumerable (c.e.) and co-infinite (i.e. its complement is infinite), but every infinite subset of its complement is not c.e.. Simple sets are examples of c.e. sets that are not computable. Simple sets were devised by Emil Leon Post in the search for a non-Turing-complete c.e. set. Whether such sets exist is known as Post's problem. Post had to prove two things in order to obtain his result: that the simple set A is not computable, and that the K, the halting problem, does not Turing-reduce to A.
