Problème algorithmique

Un problème algorithmique est, en informatique théorique, un objet mathématique qui représente une question ou un ensemble de questions auxquelles un ordinateur devrait être en mesure de répondre. Le plus souvent, ces problèmes sont de la forme : étant donné un objet (l'instance), effectuer une certaine action ou répondre à telle question. Par exemple, le problème de la factorisation est le problème suivant : étant donné un nombre entier, trouver un facteur premier de cet entier. On distingue en particulier deux types de problèmes : les problèmes de décision, qui consistent à répondre oui ou non à une question (par exemple, cet entier est-il premier ?) ; les problèmes à promesse, qui consistent à répondre oui ou non à une question uniquement sous une hypothèse (la promesse) ; les problèmes de recherche (ou de fonction), qui consistent à produire un objet spécifié par l'énoncé du problème (par exemple, la factorisation). Les problèmes algorithmiques jouent un rôle central en informatique théorique et forment un domaine à part entière, à côté de celui des algorithmes qui étudient les méthodes efficaces de résolution de problèmes décidables et de celui de l'analyse de la complexité des algorithmes qui cherche à comprendre les performances de ces algorithmes. Un problème algorithmique est le plus souvent formulé par un ensemble dentrées possibles, appelées instances, et des contraintes sur la sortie. L'algorithme doit pouvoir calculer, à partir de l'instance, une sortie qui satisfait les contraintes en question. En d'autres termes, une instance est un ensemble de données d'entrée qui satisfont les contraintes imposées par l'énoncé d'un problème algorithmique. Un problème peut être décidable ou indécidable. Un problème est décidable s'il existe un algorithme pour le résoudre. Une fois la décidabilité démontrée, une deuxième question se pose, concernant l'efficience de la recherche d'une solution. Dans ce cas il faut fixer une représentation des données et des solutions du problème pour pouvoir dire quelque chose sur la complexité.