A la hora de demostrar que un problema pertenece a NP, cuando se describe un certificador eficiente para el problema ¿Es necesario indicar cómo se codifica cada una de sus entradas como una tira de bits (por ejemplo, para el problema de ciclo hamiltoniano, cómo codificar un grafo)?
hola Nicolás
sí, es necesario, aunque como habrás visto en las soluciones de los parciales viejos, no siempre escribimos una especificación muy detallada. En el caso de un grafo, puede decirse que puede representarse como una tira de bits a partir de su matriz de adyacencias, creando un array a partir de las filas de la matriz. la razón de esta necesidad es que la restricción de tamaño polinómico de t en función de s debe ser explícita y evidente.
saludos
Javier
Buenísimo gracias por tu respuesta. A la hora de escribir el algoritmo del certificador, es necesario acceder a los parámetros cómo tiras de bits, o se puede escribir en alto nivel?
hola
se puede escribir en alto nivel.
saludos
J