Buenas, quería consultar si esta demostración del Ejercicio 1a del práctico 12 es válida.
Buenas,
La respuesta creo que está bastante bien, pero le faltan algunas cosas. Por ejemplo, falta mostrar que la transformación propuesta se puede realizar en tiempo polinomial sobre el tamaño de la entrada.
Por otro lado, el enunciado que se demuestra al final está un poco ambiguo.
En general lo que hacemos es presentar un enunciado de este tipo:
"Demostramos que
es una instancia SI de Interval Scheduling 
la transformación de es una instancia SI de Independent Set".
Luego procedemos a demostrar el directo y el recíproco.
Por último, quería señalarte que este ejercicio tiene una solución más trivial que viene de utilizar la definición de
. Un problema se reduce en tiempo polinomial a otro si en una cantidad polinomial de pasos sobre el tamaño de la entrada, y una cantidad polinomial de llamadas a una caja negra del otro problema, se puede obtener la solución del primero.
Como Interval Scheduling es un problema con una solución en tiempo polinomial conocida, es decir
, se cumple que 
, ya que con una cantidad polinomial de pasos podemos obtener la solución de IS, sin tener que recurrir a ninguna caja negra.
Saludos,
Guillermo
La respuesta creo que está bastante bien, pero le faltan algunas cosas. Por ejemplo, falta mostrar que la transformación propuesta se puede realizar en tiempo polinomial sobre el tamaño de la entrada.
Por otro lado, el enunciado que se demuestra al final está un poco ambiguo.
En general lo que hacemos es presentar un enunciado de este tipo:
"Demostramos que
es una instancia SI de Interval Scheduling la transformación de es una instancia SI de Independent Set".Luego procedemos a demostrar el directo y el recíproco.
Por último, quería señalarte que este ejercicio tiene una solución más trivial que viene de utilizar la definición de
. Un problema se reduce en tiempo polinomial a otro si en una cantidad polinomial de pasos sobre el tamaño de la entrada, y una cantidad polinomial de llamadas a una caja negra del otro problema, se puede obtener la solución del primero.Como Interval Scheduling es un problema con una solución en tiempo polinomial conocida, es decir
, se cumple que , ya que con una cantidad polinomial de pasos podemos obtener la solución de IS, sin tener que recurrir a ninguna caja negra.Saludos,
Guillermo