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 solution 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. D'un point de vue formel, un problème est décrit par un ensemble de solutions, autrement dit par un prédicat.

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é, un problème de décision implique très généralement la question de sa décidabilité. Il s'agit alors de rechercher l'existence et d'expliciter un algorithme en vue de résoudre le problème avec celui-ci. Dans le cas, où pour un problème donné, il n'existe pas d'algorithme le résolvant, le problème est dit indécidable. Il arrive par conséquent que les problèmes les plus intéressants sont généralement indécidables tels que le problème de l'arrêt.

La formalisation la plus répandue est celle de machine de Turing cependant la thèse de Church-Turing affirme que les machines de calcul sont en général toutes équivalentes.

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-complet n'aura pas de solution exacte en pratique, sauf sur des cas particuliers ou sur des instances de taille suffisamment petite.

Voir aussi[modifier | modifier le code]