Hola tenia una consulta respecto a este ejercicio en la parte B. Entiendo porque para d = 0 funciona dicha solucion, pero no entiendo que criterio usa para igualar d=0 y de esa forma descartar el resto de los posibles valores de d.
hola ignacio, en este caso la reducción polinomial que interesa probar es de IS hacia Cocinero. En tal caso, el valor de 'd' que se ajusta para cualquier IS es d=0 ya que en la definición de IS no tenemos tolerancia alguna: no admitimos ninguna incompatibilidad entre ingredientes. lo que (considerando la transformación de la solución) para el caso de IS sería justamente, vértices que no se vinculan a través de ningúna arista.
resumen, necesitamos una forma (transformación de un problema en otro) de resolver IS a partir de una caja negra que resuelve Cocinero (y no a la inversa, en cuyo caso si deberíamos poder resolver para diferentes 'd's).
saludos
resumen, necesitamos una forma (transformación de un problema en otro) de resolver IS a partir de una caja negra que resuelve Cocinero (y no a la inversa, en cuyo caso si deberíamos poder resolver para diferentes 'd's).
saludos
En respuesta a Facundo Benavides
Re: Ejercicio 3 - examen julio 2022
Hola
No pude asistir a la consulta de hoy
Tengo una duda respecto al ejercicio 1 de febrero 2020
En la instancia de PCG que muestran de ejemplo cual sería el subconjunto /arista que contiene a 9 ?
No toda representación de subconjuntos se puede representar con un grafo
No pude asistir a la consulta de hoy
Tengo una duda respecto al ejercicio 1 de febrero 2020
En la instancia de PCG que muestran de ejemplo cual sería el subconjunto /arista que contiene a 9 ?
No toda representación de subconjuntos se puede representar con un grafo