Hola a todos,
Investigando ejercicios sobre temas de complejidad P y NP me encontré con este ejercicio agradecería cualquier accesoria
Una fórmula proposicional Φ esta en forma normal disyuntiva (FND), si es una disyunción de conjunciones de literales, es decir, tiene la forma
Φ ≡ { P11^P12^ .. ^P1k1 } ∨ { P21^P22^ .. ^P2k1 } ∨ ... ∨ { Pr1^Pr2^ .. ^Prkr }
La fórmula Φ depende de los símbolos preposicionales a1, a2, ... , an. Cada Pij es un literal, es decir es au o ¬au para algún (u que ésta entre 1..n)
Se sabe que toda fórmula proposicional α tiene una fórmula proposicional Φ equivalente, en FND
a) Describa un algoritmo para decidir la satisfacibilidad de la fórmula Φ
b) Demuestre que, dada una fórmula de lógica proposicional α (a1, ..., an), el problema x que consiste en construir una fórmula Φ tal que ( Φ ≡ α)
No es polinomial, si P≠NP
Ayuda: Suponga que sí lo es y pruebe que esto llevaría a que algún problema en NPC tuviera solución polinomial.
Agradezco cualquier ayuda de antemano
