Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Problème de décision

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é les distances entre les villes d'une carte 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.

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 décidables en pratique pour des raisons de trop grande complexité des calculs  la théorie de la complexité donne une hiérarchie des complexités formelles. En particulier, un problème NP-complet sera non résoluble exactement en pratique, sauf sur des cas particuliers ou sur des instances de taille suffisament petite.