hola Leandro:
en la linea de la respuesta que mandé hace un rato a una consulta de otro compañero, te comento:
En el caso de un ejercicio en el que pidamos demostrar que algo es NP, lo que nos parece más importante es que nos muestres que entendés los elementos que definen a un problema NP. Es decir, que un problema X es NP si existe un certificador eficiente para él. Ese certificador es un algoritmo, B, de tiempo polinómico que toma dos argumentos de entrada s y t, una solución y un certificado. Debe existir una función polinómica p tal que para cada cadena s, s pertenece al conjunto de las soluciones SÍ de X si y sólo si existe una cadena t tal que |t| ≤ p(|s|) y B(s, t) = SÍ.
Todos esos son aspectos que debés que mencionar para el problema particular que aparezca en un ejercicio. Explicar cuál es el algoritmo certificador, explicar qué es y que forma tienen la solución s y el certificado t.
No es tan importante que demuestres formalmente que |t| ≤ p(|s|) o que B es de tiempo polinómico. Si no aclaramos otra cosa, en el contexto de un examen o parcial no exigiriamos eso para dar todos los puntos.
saludos,
Javier
