Dadas dos fórmulas booleanas (también conocidas como circuitos lógicos), quiero comprobar si son lógicamente equivalentes, es decir, si calculan la misma tabla de verdad. ¿Es un problema NP-completo? ¿Cuál es la prueba?
Respuesta
¿Demasiados anuncios?
Andrea Girardi
Puntos
130
En realidad es co-NP-Completo .
Aquí está la prueba.
Primero tenemos que demostrar que está en co-NP . Esto no es difícil, ya que es rápido verificar un contraejemplo que demuestre que las dos fórmulas booleanas no son equivalentes.
Entonces tenemos que demostrar que un problema conocido como co-NP-completo se reduce a su problema, que llamaremos Equivalencia Booleana. Reduciremos el problema de la Tautología a la Equivalencia Booleana. Así que si queremos determinar si un wff dado $\phi$ es una Tautología, simplemente enviamos las fórmulas $\phi$ et $a \vee \neg a$ en el comprobador de equivalencia booleana. Como esto se puede hacer en tiempo polinómico, hemos terminado.
