Hola, buenas tardes.
Tengo que hacer una exposición ilustrando de manera simple la demostración de este articulo
https://people.csail.mit.edu/rivest/pubs/BR92.pdf, pero le he dado vueltas por dos días y no he conseguido entenderlo. (La demostración del teorema 1 y 2).
No entiendo por qué se elige un arreglo tan especifico para demostrar que el Set-Splitting es equivalente al Quadrant of Positive Boolean Examples problem (Restricción del problema original) ¿No se estaría demostrando que esa instancia especifica del problema es NP-completo? no entiendo por qué demostrar que esa instancia es NP-completo demostraría que todo el problema es NP-completo. Además, no entiendo por qué, luego de demostrar que el Quadrant of Positive Boolean Examples problem es NP-completo, dicho se puede extender poniendo tres dimensiones nuevas \( x_1, x_2, x_3 \) para así demostrar el teorema 1.
Espero que alguien pueda ayudarme. Gracias de antemano.
