Cambalache 3,14 - La vidriera irrespetuosa

Definición: Problema 2-1EQSAT

ENTRADA: Un conjunto de variables U={up} y un conjunto de cláusulas generalizadas C={cq} sobre U, siendo cada una de ellas la disyunción de un literal con una equivalencia lógica de literales de variables de U: [u,v≡w].

PREGUNTA: ¿Existe una asignación de verdad para U que satisfaga C?

Teorema: 2-1EQSAT es NP-completo.