Práctico 11 - Sobre alcance de lo que piden los ejercicios.

Práctico 11 - Sobre alcance de lo que piden los ejercicios.

de Marco Liguori Hernandez -
Número de respuestas: 4

Buenas,

Mi consulta va orientada a que cosas podemos tomar demostradas o probadas y que otras no. Dos ejemplos concretos:

1) En el ejercicio 1 del Práctico 11, hice una reducción de Interval Scheduling a Independent Set, para luego usar la transitividad de las reducciones polinómicas , usando que Indep. Set <=p Vertex Cover, obtengo que Interval Scheduling <=p Vertex Cover. Mi pregunta sería si debo demostrar que Indep. Set <=p Vertex Cover para utilizar el restulado. Dado que son problemas algo así como "canónicos" y la prueba está en el libro, pensé quizás que no era necesario.

2) Para demostrar una reducción como la del ejercicio 3. ¿Es necesario demostrar que pasar de un grafo como el que toma Independent Set a una tabla como la de Conjunto Diverso toma tiempo polinómico? De ser si la respuesta ¿asumo que siempre hay que demostrar que toma una cantidad polinómica de pasos preprocesar los datos para resolverlos con la caja negra y así completar la demostración?.

Desde ya muchas gracias,

Marco.

En respuesta a Marco Liguori Hernandez

Re: Práctico 11 - Sobre alcance de lo que piden los ejercicios.

de Javier Baliosian -
hola Marco:

tus dudas son muy razonables. las respuestas no siempre son las mismas porque en algún caso nos puede interesar que nos cuentes, como si fuera una pregunta del teórico, cómo se reduce Independent Set a Vertex Cover, en ese caso lo diríamos explícitamente. Las respuestas genéricas, a no ser que aclaremos algo en la letra de un ejercicio, serían:

sobre la pregunta 1), sí, podes considerar como conocimiento "teórico" que Independent Set <=pVertex Cover, pero debes decirlo explícitamente, no darlo por asumido. No es el foco de tu pregunta, pero quiero hacerte notar que en ese ejercicio no es necesario hacer la reducción, Interval Scheduling se resuelve en tiempo polinómico por lo tanto hay una reducción trivial que es simplemente resolver el problema. 

sobre la pregunta 2), lo que esperamos de este tipo de ejercicios es que sepas y entiendas la pregunta básica "¿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 VC? 
llevándolo a tu pregunta, lo importante ahí es que nos muestres cómo transformas una instancia del problema IS en una instancia del problema VC y que ademas digas que se puede hacer en tiempo polinómico (en general es evidente, si no lo fuera sí deberías darnos mas pistas pero lo pediríamos explícitamente). no olvides que también se debe demostrar que utilizando esa transformación toda respuesta Sí de del VC implica una respuesta Sí al IS y toda respuesta Sí al IS implica una respuesta SÍ al VC.

saludos
J




En respuesta a Javier Baliosian

Re: Práctico 11 - Sobre alcance de lo que piden los ejercicios.

de Marco Liguori Hernandez -
Buenas Javier,

Respecto a tu respuesta 1: No me quedó claro a que te referías con que "no es necesario hacer la reducción...". A pesar de que Interval Scheduling ya de por sí pertenece a P, para demostrar lo requerido (Interval Scheduling <=p Vertex Cover) tengo que sí o sí hacer una transformación del problema IS al tipo de "input" que recibe Vertex Cover ¿verdad? (en mi caso lo hice con Independent Set pero la pregunta se mantiene).

Respecto a la respuesta 2: Creo que me responde la pregunta 1. Pero dejo abierta el párrafo de arriba por las dudas que no haya entendido.

Gracias y saludos.
En respuesta a Marco Liguori Hernandez

Re: Práctico 11 - Sobre alcance de lo que piden los ejercicios.

de Javier Baliosian -
hola Marco:
quizás lo que pasa es que al decir que no es necesario hacer la reducción estoy abusando un poco del lenguaje. lo que no es necesario es transformar la instancia de IS en una de VC. Si te fijas en la pregunta que puse antes, que está copiada de la que figura en la pagina 452 del libro y que incluye ala definición de "reducible en tiempo polinómico" dice "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 VC". en este caso, el número polinómico de pasos es el necesario para resolver IS y número polinómico de llamadas a la caja negra sería 0, o podría ser 1 con una instancia trivial de VC.
capaz que queda más claro así.
saludos
Javier