¿Cómo probarías que el problema máximo de conjunto independiente en los gráficos está en la clase NP?

Una definición informal útil de la clase NP es que contiene todos los problemas para los cuales, una vez que se le da una solución, es fácil verificar que la solución realmente funciona. (Esto se puede convertir en una definición formal, pero probablemente no sea muy útil).

Ahora, como una nota técnica (aún hablando informalmente), la clase NP se define solo para problemas cuya respuesta es sí o no. Entonces, la pregunta que queremos responder no es “¿Qué tan grande es el conjunto independiente más grande?” En cambio, preguntamos: “¿Hay un conjunto independiente de tamaño k?”

Si existe tal conjunto, y alguien le entrega una lista de los k nodos que pertenecen a él, puede verificar fácilmente (es decir, en tiempo polinómico) cada par de nodos posible y asegurarse de que ninguno de ellos esté conectado. Esto es suficiente para demostrar que la solución propuesta es válida, es decir, que la lista de nodos es un conjunto independiente.

Por lo tanto, dado que una solución se puede verificar fácilmente, este problema está en la clase NP.