Problème de décision

Cet article est une ébauche concernant l’informatique et les mathématiques. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

On parle de problème de décision dans des contextes variés. Cet article est destiné à décrire ce terme en informatique, ou en mathématiques.

En algorithmique, un problème de décision est une question mathématiquement définie portant sur des paramètres donnés sous forme manipulable informatiquement, et demandant une réponse par oui ou non.

Ainsi, savoir si, étant donné un ensemble de villes et une distance d, il existe un chemin passant par toutes les villes et de longueur inférieure à d, est un problème de décision (en l'occurrence, le problème du voyageur de commerce).

Un problème de décision peut être indécidable s'il n'existe aucun programme informatique qui permette de le résoudre (sans restriction de mémoire ou temps), ce que l'on formalise par l'impossibilité de répondre au problème à l'aide d'une machine de Turing.

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.

[modifier] Voir aussi

• Problème de la décision