Problème algorithmique

En informatique théorique, un problème est un objet mathématique qui représente une question ou un ensemble de questions. Le plus souvent ces problèmes sont de la forme : étant donné une un objet (l'instance), faire ceci ou répondre à telle question. Par exemple le problème de la factorisation est le problème suivant : étant donné un entier, trouver un facteur 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ème d'évaluation ou de construction, qui consiste à produire un nouvel objet.