Problème de décision

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 encore le problème du voyageur de commerce.

Dans le contexte de la calculabilité[modifier | modifier le code]

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. Dans le cas où, au contraire, il n'existe pas d'algorithme résolvant le problème, celui-ci 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.

Dans le contexte de la théorie de la complexité[modifier | modifier le code]

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 est considéré comme tellement difficile qu'on admet qu'il n'y a pas d'algorithme un tant soit peu efficace qui le résolve. Si on monte dans la hiérarchie les problèmes deviennent encore plus difficiles et les algorithmes sont alors impossibles à exécuter en temps raisonnable.

Voir aussi[modifier | modifier le code]