Buenas,
Primero hay que ver que tenemos que demostrar.
En este ejercicio tenemos la reduccion Independent Set ≤ p Conjunto Diverso.
A grandes rasgos significa que tenemos que usar el problema Conjunto Diverso para resolver Independent Set.
Por lo tanto para demostrar esta reducción:
- Independent Set tiene como entrada un grafo G y un k.
Por lo que se podría utilizar este grafo G para generar una instancia del problema de Conjunto Diverso y con un numero polinomial de llamadas (una sola llamada quizá) resolver el problema.
Primero hay que ver que tenemos que demostrar.
En este ejercicio tenemos la reduccion Independent Set ≤ p Conjunto Diverso.
A grandes rasgos significa que tenemos que usar el problema Conjunto Diverso para resolver Independent Set.
Por lo tanto para demostrar esta reducción:
- Independent Set tiene como entrada un grafo G y un k.
Por lo que se podría utilizar este grafo G para generar una instancia del problema de Conjunto Diverso y con un numero polinomial de llamadas (una sola llamada quizá) resolver el problema.
¿Que recibe Conjunto Diverso? Recibe una tabla A (de clientes y productos) y un k'.
Por lo que una posible solución podría ser transformar el grafo G en una tabla A y decidir cual deberia ser el valor de k' (probablemente en funcion del k de Independent Set).
Luego de demostrar porque el numero de llamadas a la 'caja negra' que resuelve Conjunto Diverso es polinomial y de demostrar porque es polinomial la transformación. Se deberia demostrar que: una instancia (G,k) de Independent Set es una instancia Si ↔ (A,k) es una instancia Si de ConjuntoDiverso.
Cualquier otra duda a las ordenes
Por lo que una posible solución podría ser transformar el grafo G en una tabla A y decidir cual deberia ser el valor de k' (probablemente en funcion del k de Independent Set).
Luego de demostrar porque el numero de llamadas a la 'caja negra' que resuelve Conjunto Diverso es polinomial y de demostrar porque es polinomial la transformación. Se deberia demostrar que: una instancia (G,k) de Independent Set es una instancia Si ↔ (A,k) es una instancia Si de ConjuntoDiverso.
Cualquier otra duda a las ordenes