Siguiente: Formas booleanas Un nivel arriba: Completitud-NP Anterior: Problemas difíciles y completos

Formas proposicionales y el teorema de Cook

Veremos que el problema de decidir si acaso una forma booleana es satisfactible es un problema completo-NP.