hola Nicolas,
en cuanto a tu primer pregunta, la respuesta es sí. En general esa prueba es muy sencilla porque el certificador suele ser un simple chequeo, por construcción como en este caso, de que el "certificado" es una solución (o no) del problema. Quizás al escribir esta solución eso era demasiado evidente y no se dijo explícitamente. Yo les recomendaría que no asuman que eso es tan evidente y nos lo expliquen. Eso nos va a ayudar a ver que ustedes estan entendiendo lo que deben hacer, incluso si cometen algún error.
en cuanto a que el certificado debe ser un string, la respuesta tambien es sí. En este caso el lenguaje usado en la solución puede llevar a confusión. La lista a la que hace referencia no es la estructura de datos con sus punteros y todo, sino una lista de posiciones como se entiende vulgarmente, una detras de la otra, facilmente implementable como un string. De nuevo, mi recomendación es que sean explícitos en ese sentido, tambien para ayudarnos a ver que entendieron la definición de NP.
saludos
Javier