Hola Lucia,
creo que es la formalizacion lo que confunde,
trato de explicarlo con un ejemplo.
Consideremos Independent Set.
En este caso:
"s" es una instancia (G,k) del problema, o sea un grafo con por ejemplo tres nodos y dos aristas, y el numero k=2.
Si queremos ver "s" como un string podríamos usar la matriz de adyacencias (como string) y concatenado el numero k=2.
"A" es un algoritmo que reciba como parámetros un grafo y un k (el string s), y retorne "SI" siempre que exista
un conjunto de nodos de tamaño al menos 2 en ese grafo sin aristas entre ellos, o "NO" .
"X" son el conjunto de "s" tal que A(s)=yes
"t" es la evidencia que "s" es SI ("solucion de s"), que seria el conjunto de nodos de la instancia "s" que no tiene aristas, podría ser una
lista o un string con los ids de nodos, en este caso el nodo 1 y el nodo 3 por ejemplo.
todo esto es para luego definir un algoritmo certificador B(s,t) que pueda chequear si la instancia "s" es si (polinomial)
para todo s en X
saludos
creo que es la formalizacion lo que confunde,
trato de explicarlo con un ejemplo.
Consideremos Independent Set.
En este caso:
"s" es una instancia (G,k) del problema, o sea un grafo con por ejemplo tres nodos y dos aristas, y el numero k=2.
Si queremos ver "s" como un string podríamos usar la matriz de adyacencias (como string) y concatenado el numero k=2.
"A" es un algoritmo que reciba como parámetros un grafo y un k (el string s), y retorne "SI" siempre que exista
un conjunto de nodos de tamaño al menos 2 en ese grafo sin aristas entre ellos, o "NO" .
"X" son el conjunto de "s" tal que A(s)=yes
"t" es la evidencia que "s" es SI ("solucion de s"), que seria el conjunto de nodos de la instancia "s" que no tiene aristas, podría ser una
lista o un string con los ids de nodos, en este caso el nodo 1 y el nodo 3 por ejemplo.
todo esto es para luego definir un algoritmo certificador B(s,t) que pueda chequear si la instancia "s" es si (polinomial)
para todo s en X
saludos