Mostrare la cricca massima è NPO-SIMPLE e la colorazione del grafico massima non lo è

Question

Ricordare la nozione di Problema NPO. Un problema NPO è semplice se è vero:

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

A parole, dato qualsiasi intero positivo $ k $, il problema di decidere se ad esempio $ x $ il suo ottimale è inferiore o uguale di k è in $ p $.

Mi viene chiesto di mostrare il problema massimo della cricca è semplice e che presupponendo $ p neq np $ la colorazione del grafico minimo non è semplice.

Riferimenti

Questo è il problema 3.13 di "complessità e approssimazione" di Ausiello et alii.