5
Sé que la satisfacibilidad booleana es NP-Completa, pero es la minimización/simplificación de una expresión booleana, con lo que me refiero a tomar una expresión dada en forma simbólica y producir una expresión equivalente pero simplificada en forma simbólica, ¿NP-Complete? No estoy seguro de que haya una reducción de la satisfaccion a la minimización, pero siento que probablemente sí exista. ¿Alguien sabe con seguridad?¿La minimización de las expresiones booleanas NP-Complete?
Escrito un poco más claramente esta podría ser la reducción que se buscaba. –
Usted y el cartel original probablemente signifiquen NP-hard. Por lo que pude averiguar, no se sabe que el problema esté en NP. – starblue
starblue: no, nos referimos a NP completo. SAT es en realidad EL problema completo de NP clásica, es decir, fue el primer problema que resultó ser NP completo, y todos los demás se redujeron directa o indirectamente a él. Esto, por cierto, todo se explica en el artículo de Wikipedia. –