Practico 11, ejercicio 3

Re: Practico 11, ejercicio 3

de Javier Baliosian -
Número de respuestas: 0

hola Alfredo 

el formato de tu pregunta es un poco inesperado. ¿Cuál es la solución que se les ocurrió a vos a tu compañero? 

en todo caso, no, no es correcta, o al menos no lo parece. El ejercicio pide que "Muestre que Independent Set ≤p Conjunto Diverso." y por lo tanto, lo que hay que mostrar es que  pueden resolverse instancias arbitrarias del problema IS utilizando un número polinómico de pasos computacionales estándar, más un número polinómico de llamadas a una caja negra que resuelve el problema CD. Por lo que entiendo de esa solución, estan haciendo lo contrario. 

saludos

J