IB102 – úkol 11, příklad 1 Odevzdání: 16. 12. 2013
Vypracoval(a): UČO:
Skupina:
1. [2 body] Definujme jazyk Triple-SAT následovně:
Triple-SAT = { Φ | Booleovská formule Φ má alespoň 3 různá splňující přiřazení }
Dokažte, že jazyk Triple-SAT je NP-úplný. Vaší úlohou je tedy ukázat, že TripleSAT
je NP-těžký (nejlépe redukcí z nějakého jiného NP-těžkého problému) a zároveň, že
patří do třídy NP. Použitou redukci co nejpřesněji popište a zdůvodněte, proč se jedná
o polynomiální redukci.
1