Réductibilité et degrés d'insolvabilité
La réductibilité compare la difficulté des problèmes en transformant l'un en l'autre, et le regroupement des problèmes de difficulté égale produit les degrés d'insolvabilité qui structurent le monde au-delà du calculable.
Definition
Un problème se réduit à un autre lorsqu'un algorithme ayant accès à un solveur pour le second peut résoudre le premier ; les problèmes qui se réduisent l'un à l'autre partagent un degré d'insolvabilité, et ces degrés forment un ordre mesurant la difficulté algorithmique relative.
Scope
Ce sujet couvre la réductibilité many-one et la réductibilité de Turing, l'utilisation des réductions pour prouver l'indécidabilité, l'opération de saut de Turing qui produit des problèmes strictement plus difficiles, la hiérarchie arithmétique classifiant les problèmes par complexité logique, et les résultats centraux de la théorie des degrés tels que l'existence de degrés intermédiaires.
Core questions
- Comment peut-on dire qu'un problème insoluble est plus difficile qu'un autre ?
- Comment les réductions sont-elles utilisées à la fois pour prouver l'indécidabilité et pour organiser les problèmes ?
- Que produit le saut de Turing, et pourquoi est-il toujours strictement plus difficile ?
- Existe-t-il des problèmes strictement entre le décidable et le problème de l'arrêt ?
Key theories
- Réductibilité et le saut de Turing
- La réductibilité de Turing relie les problèmes par le calcul avec oracle, et le saut d'un problème, encodant l'arrêt par rapport à celui-ci, est toujours strictement plus difficile, générant une tour infinie de problèmes de plus en plus difficiles.
- Existence de degrés intermédiaires
- Le théorème de Friedberg-Muchnik a résolu le problème de Post en construisant des problèmes récursivement énumérables qui sont indécidables mais strictement plus faciles que le problème de l'arrêt, en utilisant la méthode de priorité, montrant que les degrés ont une structure riche.
Clinical relevance
La technique de réduction est l'outil quotidien pour prouver l'insolvabilité des problèmes ou, en théorie de la complexité, leur intratabilité : montrer qu'un problème difficile connu se réduit à un nouveau transfère la difficulté, ce qui est précisément la manière dont les résultats d'indécidabilité et de NP-complétude sont établis en mathématiques et en informatique.
History
Turing a introduit les machines à oracle en 1939, et Post, en 1944, a encadré l'étude des degrés d'insolvabilité et a posé le problème de l'existence de degrés intermédiaires récursivement énumérables. Friedberg et Muchnik l'ont résolu indépendamment en 1956-1957 en inventant la méthode de priorité, qui est devenue une technique centrale du domaine.
Key figures
- Emil Post
- Alan Turing
- Richard Friedberg
- Albert Muchnik
Related topics
Seminal works
- soare2016
- rogers1987
Frequently asked questions
- Qu'est-ce qu'une réduction, intuitivement ?
- C'est une manière de résoudre un problème en utilisant un solveur pour un autre. Si vous pouvez traduire toute instance du problème A en une instance du problème B de sorte que les réponses correspondent, alors B est au moins aussi difficile que A, et une solution à B donne une solution à A.
- Existe-t-il des problèmes plus difficiles que le problème de l'arrêt ?
- Oui, une infinité. Appliquer le saut de Turing au problème de l'arrêt produit un problème strictement plus difficile, et répéter l'opération construit une hiérarchie sans fin, ainsi l'insolvabilité se présente sous des degrés illimités plutôt qu'un seul niveau.