IB107 Vyčíslitelnost a složitost další NP-úplné problémy, prostorová složitost vztahy složitostních tříd Jan Strejček Fakulta informatiky Masarykova univerzita problém VERTEX-COVER Definice (vrcholové pokrytí) Necht G je neorientovaný graf. Podmnožina jeho vrcholů se nazývá vrcholové pokrytí grafu G, pokud obsahuje alespoň jeden vrchol každé hrany grafu G. Definice (problém VERTEX-COVER) Problém VERTEX-COVER je problém rozhodnout, zda daný graf G má vrcholové pokrytí obsahující právě daný počet vrcholů k. VERTEX-COVER = {(G, k) \ G je graf s vrcholovým pokrytím obsahujícím právě k vrcholů } IB107 Vyčíslitelnost a složitost: další NP-úplné problémy, prostorová složitost, vztahy složitostních tříd 2/20 VERTEX-COVER je NP-úplný Věta VERTEX-COVER je NP-úplný. Důkaz: VERTEX-COVER e NP: VERTEX-COVER je NP-těžký: 3SAT

2, c2,..., a/5 Ď/, c/} u {x, -.x \ x e X} a ■ E ={{ah b,}, {ah c,}, {bh q} | 1 < / < /} u {{x, -x} | x g X} u u "hrany mezi literálem a shodným vrcholem x nebo -ix" (p = (x v y v z) a (-.x v -i/ v -.z) a (x v ^y v -, u}, >, u, S, q0, qacc, qrej) s > 0 1 u qo (qo, >, R) (Qo,0,fí) (Qi, 1, {qacc, ~, ") q^ (Qrej, ~, -) (qacc, —, ") IB107 Vyčíslitelnost a složitost: další NP-úplné problémy, prostorová složitost, vztahy složitostních tříd 11/20 komprese prostoru Pro každý deterministický úplný TM m a pro každé m > 1 lze zkonstruovat deterministický úplný TM m' tak, že L(m) = L(mř) a Důkaz: SM,(n) = SM(n) m + A7 + 2. Protože prostor lze komprimovat, používame asymptotickou notaci. IB107 Vyčíslitelnost a složitost: další NP-úplné problémy, prostorová složitost, vztahy složitostních tříd 12/20 prostorové složitostní třídy problémů prostorová složitost problému = nejmenší prostorová složitost, s jakou lze daný problém rozhodnout Definice 2.3 (prostorové složitostní třídy problémů) Každá funkce f: N -> IRq definuje prostorové složitostní třídy problémů: SPACE(f(n)) = {L | L je rozhodovaný nějakým det. TM m s prostorovou složitostíSM(n) = 0(f(n))} NSPACE(f(n)) = {L | L je rozhodovaný nějakým nedet. TMAÍ s prostorovou složitostí Sx(n) = 0(f(n))} IB107 Vyčíslitelnost a složitost: další NP-úplné problémy, prostorová složitost, vztahy složitostních tříd 13/20 SAT e SPACE(n) SAT = {((p) | (p je splnitelná výroková formule} S/47 může být rozhodován deterministickým třípáskovým TM m\ ■ na 2. pásku postupně zapisujeme všechna ohodnocení proměnných ■ na 3. pásce pro dané ohodnocení ověříme, zda splňuje

• Rq platí: D TIME(f(n)) c NTIME(f(n)) U SPACE{f{n)) c NSPACE(f(n)) □ TIME(f(n)) c SRACE(ř(n)) □ NTIME(f(n)) c NSPACE{f{n)) m SPACE(f(n)) c U,€N TIME(kf(n)) m NSPACE{f{n)) c y^eN NTIME{kfW) Důkaz: IB107 Vyčíslitelnost a složitost: další NP-úplné problémy, prostorová složitost, vztahy složitostních tříd 15/20 Savitchova věta Pro každou funkci f: N IRq splňující f(ri) > n platí: NSPACE(f(n)) c SPACE(f2(n)) Standardní převod nedet. TM na deterministický nefunguje: IB107 Vyčíslitelnost a složitost: další NP-úplné problémy, prostorová složitost, vztahy složitostních tříd 16/20 Savitchova věta Důkaz: Nechí Aí \e nedet. TM s prostorovou složitostí f{ri). Stroj upravíme tak, aby před akceptováním smazal pásku a posunul hlavu zcela vlevo. Má tedy jen jednu akceptující konfiguraci cacc. Výpočet stroje má maximálně kf^ kroků. Ekvivalentní deterministický stroj M implementuje proceduru comp{c^, c2, ř), která akceptuje, pokud lze ve stroji J\f během nejvýše t kroků přejít z konfigurace c-i do c2, jinak zamítá. Je-li c„ iniciální konfigurace stroje J\f pro w, stačí tedy spustit comp(cw,cacc,kŤW). comp{c^, c2, ř) lze implementovat rekurzivně: IB107 Vyčíslitelnost a složitost: další NP-úplné problémy, prostorová složitost, vztahy složitostních tříd 17/20 Savitchova věta Algoritmus pro comp{c^, c2, t)\ t = 1: Otestujeme, zda platí c-i = c2 nebo Ci \rr Cz- N Pokud platí, akceptujeme, jinak zamítneme. t > 1: Pro každou konfiguraci ď stroje J\f využívající nejvýše f(n) políček ■ spustíme comp{c^, ď, [|]) a comp(cř, c2, [|J)> ■ pokud obojí akceptuje, akceptujeme. Pokud žádné d nevedlo k akceptování, zamítneme. Prostorová složitost: ■ comp potřebuje prostor na c-i, c2, d a t (a něco konstantního): ■ hloubka rekurzivního volání: ■ celkem: ■ IB107 Vyčíslitelnost a složitost: další NP-úplné problémy, prostorová složitost, vztahy složitostních tříd 18/20 polynomiální prostorové složitostní třídy PSPACE = |J SPACE(n/c) NPSPACE = |J NSPACE^) Věta PSPACE = NPSPACE Důkaz: Plyne přímo z definice (c) a ze Savitchovy věty Q). IB107 Vyčíslitelnost a složitost: další NP-úplné problémy, prostorová složitost, vztahy složitostních tříd vztahy prostorových a časových tříd PCNPC NPSPACE = PSPACE c EXPTIME c NEXPTIME IB107 Vyčíslitelnost a složitost: další NP-úplné problémy, prostorová složitost, vztahy složitostních tříd 20/20