Correcciones TP3

[mbuchwald]

Hola! Dejo por acá las correcciones:

• Sobre la demostración de si el problema está en NP, ver la cantidad de elementos de un conjunto es de tiempo constante. ¿De dónde sale el logaritmo? Luego, constante o logarítmico, $mathcal{O}(\log k + k)$ es $\mathcal{O}(k)$ (estoy obviando la n, que por supuesto sigue estando).
• A la demostración de ser NP-Completo le falta algo: no hay límite en elegir una variable y su complemento (que sería nuestra interpretación de ser true o false). ¿Por qué dicen además que supongamos k = 2? ¿Ponen alguno cualquiera? Si mis cláusulas son $x_1$ y $~x_1$ (por separado), entonces si K = 2 van a decir que es en efecto posible obtener un hitting set de tamaño 2 cuando la expresión no es satisfacible. Esto lo van a tener que volver a hacer. Como recomendación: vayan por 3-SAT, de paso se simplifican un poco (la reducción es en sí la misma en ambos casos, pero al menos se simplifican un poco para pensarlo mejor).
• No pude ejecutar el programa como ponen en el readme. Lo traté de ejecutar desde este nivel tal cual indican en el readme (poetry run python tp3/selector.py <.....>/200_bis.txt, para ejecutar una prueba), y de otras formas, y hasta sin poetry, pero siempre tuve el mismo error:

  
  Traceback (most recent call last):
  File "/Users/mbuchwald/Downloads/tda-i-tps/tp3/tp3/selector.py", line 3, in <module>
  from tp3.archivos import *
  ModuleNotFoundError: No module named 'tp3'

* No está enunciado el modelo de programación lineal. Tuve que deducirlo de ver el código. 
* No está hecha la demostración de la cota del algoritmo de aproximación que nosotros les propusimos. 
* Al análisis del algoritmo greedy propuesto por ustedes habría estado bueno que le calculen una cota de aproximación empírica (no pedimos demostrada, pero al menos algo de análisis por ese lado). 

Dicho esto, les pido que reentreguen al menos con la demostración correcta que el problema es NP-Completo, y la cota de aproximación del algoritmo de aproximación. 
Lo demás es opcional. Y me indiquen qué debo hacer para poder ejecutar el programa para terminar de hacer unas validaciones. 

[mrti259]

Reescribo para llevar registro de los cambios para la reentrega:

• [x] Sobre la demostración de si el problema está en NP, ver la cantidad de elementos de un conjunto es de tiempo constante. ¿De dónde sale el logaritmo? Luego, constante o logarítmico, O(log k + k) es O(k) (estoy obviando la n, que por supuesto sigue estando).
• [x] A la demostración de ser NP-Completo le falta algo: no hay límite en elegir una variable y su complemento (que sería nuestra interpretación de ser true o false). ¿Por qué dicen además que supongamos k = 2? ¿Ponen alguno cualquiera? Si mis cláusulas son x1 y x1 (por separado), entonces si K = 2 van a decir que es en efecto posible obtener un hitting set de tamaño 2 cuando la expresión no es satisfacible. Esto lo van a tener que volver a hacer. Como recomendación: vayan por 3-SAT, de paso se simplifican un poco (la reducción es en sí la misma en ambos casos, pero al menos se simplifican un poco para pensarlo mejor).
• [x] No pude ejecutar el programa como ponen en el readme. Lo traté de ejecutar desde este nivel tal cual indican en el readme (poetry run python tp3/selector.py <.....>/200_bis.txt, para ejecutar una prueba), y de otras formas, y hasta sin poetry, pero siempre tuve el mismo error:
• [x] No está enunciado el modelo de programación lineal. Tuve que deducirlo de ver el código.
• [x] No está hecha la demostración de la cota del algoritmo de aproximación que nosotros les propusimos.
• [x] Al análisis del algoritmo greedy propuesto por ustedes habría estado bueno que le calculen una cota de aproximación empírica (no pedimos demostrada, pero al menos algo de análisis por ese lado).

[mbuchwald]

Ahí revisé la nueva versión. En su momento (enunciado del TP1) les habíamos pedido que agreguen las correcciones como un anexo para no tener que volver a leer todo el informe. O al menos en dicho anexo poner dónde se hicieron modificaciones o cuáles fueron.

Dicho eso, no está la modificación sobre la demostración que el problema es NP-Completo. No hay nada que asegure que no se elija una variable y su complemento. Por poner un ejemplo: supónganse que tengo 3 variables, y 8 cláusulas con todas las combinaciones posibles (normal y complementadas). Es decir, este es un caso que no se puede cumplir. Si eso se lo pasan a HItting-Set con k = 3, Hitting-Set va a decir "obvio pa que se puede", devolviendo un true que no es correcto.

Edit: por si no se entiende el caso que menciono, es este: $(x_1 \lor x_2 \lor x_3) \land (x_1 \lor x_2 \lor \overline{x_3}) \land (x_1 \lor \overline{x_2} \lor x_3) \land (x_1 \lor \overline{x_2} \lor \overline{x_3} ) \land (\overline{x_1} \lor x_2 \lor x_3) \land (\overline{x_1}\lor x_2 \lor \overline{x_3}) \land (\overline{x_1} \lor \overline{x_2} \lor x_3) \land (\overline{x_1} \lor \overline{x_2} \lor \overline{x_3}) $

[mbuchwald]

Ahora obviamente abóquense al recuperatorio. Damos tiempo hasta el domingo para que esté eso

[mbuchwald]

Corregido. Ya con esto cerramos el tp con 6 :)