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 « oui » ou « non ». Le problème soulève la question de l'existence d'un algorithme renvoyant une solution à la question posée par le problème. D'un point de vue formel, un problème est décrit par un ensemble de solutions. Il s'agit alors de raisonner sur l'ensemble des solutions au problème afin de raisonner sur le problème lui-même. La notion de codage intervient, dans la mesure où celle-ci permet d'identifier la structure sur laquelle le problème est posé.

Les problèmes se déclinent généralement en deux classes : la théorie de la calculabilité et la théorie de la complexité. Quelques exemples connus de problèmes de décision existent tels que le problème de l'arrêt, le problème de correspondance de Post ou encore le problème du voyageur de commerce en théorie de la complexité.

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

En théorie de la calculabiltié, un problème de décision implique très généralement la question de 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]