Instances

Une instance d'un problème s'obtient en précisant les valeurs des données. Par exemple,

• Données : un graphe $G$ complet d'ordre $10$, $k = 9$
• Question : $G$ est-il $k$-colorable ?

On résout un problème de décision et décidant, pour toute instance $I$, si cette instance est à réponse oui ou à réponse non. On dit plus généralement qu'un algorithme qui résout un problème de décision décide ce problème, et toutes les instances de ce problème.