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).
julitaras
commented
10 months ago
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).