Problème de décision
En 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.
Dans le contexte de la calculabilité
En théorie de la calculabilité, formuler un problème de décision c'est se poser une question de décidabilité. Il s'agit en fait de rechercher l'existence d'un algorithme résolvant le problème et, s'il existe, de l'expliciter. On dit qu'un problème (de décision) P est décidable si l'ensemble A des éléments qui répondent « oui » à la question posée est récursif. De même, P est dit partiellement décidable, semi-décidable ou prouvable si l'ensemble A est récursivement énumérable. Et dans le cas contraire, où le problème P n'est ni décidable, ni partiellement décidable, il est dit indécidable. Il y a des problèmes fondamentaux qui sont indécidables, c'est le cas du problème de l'arrêt.
Exemple
L'ensemble des nombres premiers est un exemple classique de problème de décision décidable. Il est en effet possible de savoir si un entier naturel est un nombre premier en vérifiant qu’aucun entier naturel le précédant, hormis , ne fait partie de ses diviseurs. Bien que l'on connaisse des méthodes beaucoup plus efficaces de test de primalité, l'existence d'une méthode correcte suffit pour établir la décidabilité.
Un exemple plus général, sortant du contexte mathématique ou informatique, serait de considérer un cas concret, afin de mieux visualiser les notions de « décidable » ou « calculable », et au contraire d'« indécidable » ou « incalculable ». Ainsi, considérons un jeu dans lequel un voyageur se déplace sur Terre avec, à chaque étape de son voyage, l'indication seule de sa prochaine destination. La question : « le voyageur atteindra-t-il Rome en cinq étapes ? » est une question décidable. En effet, on peut y répondre par « oui » ou par « non » simplement en effectuant son parcours et ainsi déterminer s'il se trouve à Rome ou non. La question : « le voyageur atteindra-t-il Rome avant la fin de son voyage ? » est une question un peu plus compliquée, mais tout de même décidable. L'astuce qui fait de ces deux questions des questions décidables est que l'on considère ces voyages en un nombre fini d'étapes. En effet, si l'on crée des algorithmes modélisant ces situations, ces algorithmes se termineront et donneront réponse à ces questions.
Si l'on considère maintenant un nombre infini d'étapes à ce voyage, on peut se poser la question : « le parcours du voyageur le mènera-t-il à Rome ? » et cette question est indécidable. En effet, on pourrait supposer que, de la même manière que pour les questions précédentes, il suffit de retracer le parcours du voyageur et de se demander, à chaque étape, s'il se trouve à Rome ou non, mais étant donné que le parcours est infini, il est possible que le voyageur atteigne Rome à la dixième étape, par exemple, comme il est possible qu'il erre éternellement, d'étape en étape, sans jamais savoir s'il pourra atteindre Rome un jour. Ainsi, si l'on modélise cette situation par un algorithme, il lui serait impossible de retourner la réponse « non » étant donné qu'il continuerait de se poser la question.
Dans le contexte de la théorie de la complexité
Certains problèmes de décision décidables sont cependant considérés comme non traitables en pratique pour des raisons de trop grande complexité des calculs. La théorie de la complexité des algorithmes donne une hiérarchie des complexités formelles. En particulier, un problème NP-complet est considéré comme tellement difficile qu'il est conjecturé qu'il n'existe pas d'algorithme polynomial qui puisse le résoudre.
