Montrer la clique maximale est la coloration du graphique NPO et maximum n'est pas

Question

Rappelez-vous la notion de Problème NPO. Un problème NPO est simple si ce qui suit est vrai:

$ forall k in mathbb {n} ^ *. ( forall x. opt (x) leq k) in p $

En mots, étant donné tout entier positif $ k $, le problème de décider si par exemple $ x $, son optimal est inférieur ou égal à K est en $ P $.

On me demande de montrer que le problème maximal de la clique est simple et que supposer la coloration de graphique minimum $ p neq np n'est pas simple.

Références

Il s'agit du problème 3.13 de "complexité et approximation" d'Ausillo et d'alié.