Problèmes de décision

Nous nous restreindrons aux problèmes de décision dans le reste du cours. Un problème de décision est spécifié par

• Des données
• Une question

Par exemple,

• Données : un graphe $G$, une constante $k$ strictement positive
• Question : $G$ est-il $k$-colorable ?