IB102 – úkol 11, příklad 1 – řešení 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. Ukážeme, že Triple-SAT je NP-těžký a že patří do třídy NP. Triple-SAT je NP-těžký Abychom ukázali, že Triple-SAT je NP-těžký, musíme dokázat, že pro každý jazyk L ∈ NP platí L ≤p Triple-SAT. Toho nejsnadněji docílíme tak, že ukážeme polynomiální redukci z nějakého NP-úplného jazyka (například jazyka SAT) na jazyk Triple-SAT. Tím zajistíme výše požadované, jelikož • každý L ∈ NP se polynomiálně redukuje na jazyk SAT (SAT je NP-úplný), • SAT se polynomiálně redukuje na jazyk Triple-SAT (jak níže ukážeme) a • složení dvou polynomiálních redukcí po sobě dokážeme simulovat v polynomiálním čase. Nyní tedy stačí sestrojit polynomiální redukční funkci z jazyka SAT na jazyk TripleSAT. Uvažme libovolnou Booleovskou formuli Φ a dvě čerstvé (tedy nevyskytující se ve formuli Φ) výrokové proměnné α a β. Sestrojme novou formuli Φ následovně: Φ = (Φ) ∧ (α ∨ β) Formuli Φ umíme lehce sestrojit v polynomiálním čase, jelikož vznikne z formule Φ pouze přidáním závorek a části ∧(α ∨ β) s konstantní délkou. Nyní stačí ukázat, že právě tato transformace představuje hledanou redukční funkci, tedy že platí Φ ∈ SAT ⇔ Φ ∈ Triple-SAT, což podle definice znamená SAT ≤p Triple-SAT. Oba směry implikace ukážeme zvlášť. „⇒“ Formule Φ je splněna v ohodnocení, ve kterém je splněna Φ, a navíc je splněno buď α nebo β (nebo obě). Jestliže tedy existuje splňující ohodnocení pro Φ, umíme jej snadno rozšířit na tři různá splňující ohodnocení Φ – v jednom bude pravdivá α a β ne, ve druhém naopak a ve třetím budou splněny obě. Zaveďme tato ohodnocení formálně: Nechť Γ: V ar → {true, false} je splňující ohodnocení formule Φ. Pak ohodnocení Γ1, Γ2, Γ3 definovaná níže jsou zjevně různými splňujícími ohodnoceními formule Φ . Γ1(x) =    true jestli x = α false jestli x = β Γ(x) jinak 1 IB102 – úkol 11, příklad 1 – řešení Odevzdání: 16. 12. 2013 Vypracoval(a): UČO: Skupina: Γ2(x) =    false jestli x = α true jestli x = β Γ(x) jinak Γ3(x) =    true jestli x = α true jestli x = β Γ(x) jinak „⇐“ Ze struktury formule Φ vyplývá, že každé její splňující ohodnocení splňuje také původní formuli Φ (Φ je konstruována jako konjunkce). Tím je tento směr implikace dokázán. Triple-SAT patří do třídy NP Jazyk Triple-SAT, stejně jako SAT, má intuitivní polynomiální verifikátor – pokud mu dodáme tři ohodnocení, lehce ověří, zdali jsou splňující (jednoduše postupně vyhodnotí zadanou formuli pro každé ohodnocení). Rozhodnout, zdali jsou tato ohodnocení navzájem různá v polynomiálním čase také není problém (sekvenčně je procházíme, dokud nenajdeme proměnnou, v níž se ohodnocení liší). Turingův stroj akceptující jazyk Triple-SAT si na začátku může nedeterministicky zvolit doplňkovou informaci (tři splňující ohodnocení) pro formuli na vstupu a pak simulovat výše uvedený polynomiální verifikátor. Pokud by formule na vstupu nepatřila do jazyka, nelze zvolit doplňkovou informaci tak, aby bylo slovo akceptováno (kdyby to šlo a verifikátor by slovo akceptoval, dostali bychom spor s předpokladem, že formule na vstupu nepatří do jazyka Triple-SAT). Jazyk Triple-SAT tedy náleží do NP. Závěr Jelikož Triple-SAT patří do třídy NP a je NP-těžký, pak je z definice NP-úplný. 2