Teoretická informatika — průběh výuky v semestru
1
Týden 14 Přednáška PSPACE, NPSPACE, PSPACE-úplnost Uvědomili jsme si nejprve, že např. pro zjištění toho, zda Bílý má nějakou strategii ve hře ŠACHY, která mu zaručuje vítězství v 200 tazích (rozumí se, že Bílý táhne maximálně 200-krát), bychom uměli celkem přímočaře sestavit algoritmus; např. zavoláme MaBilyVS(VychoziPozice, Bílý, 200), kde
MaBilyVS(Pozice, NaTahu, Limit): if ((Pozice, NaTahu) představuje mat Černému) return ANO; if ((Pozice, NaTahu) představuje pat nebo mat Bílému nebo Limit=0) return NE; if (NaTahu=Bílý) {Postupně pro každý tah Bílého v Pozice zavolej MaBilyVS(Pozice’, Černý, Limit), kde Pozice’ vznikne z Pozice provedením příslušného tahu; když je v nějakém případě vráceno ANO, tak return ANO, jinak return NE}; if (NaTahu=Černý) {Postupně pro každý tah Černého zavolej MaBilyVS(Pozice’, Bílý, Limit-1); když je ve všech případech vráceno ANO, tak return ANO, jinak return NE}. Snadno si ovšem spočteme, že odpovědi bychom se od tohoto algoritmu nedočkali, ale není to tím, že by přetekla paměť. Je snadno vidět, že pro přirozenou implementaci v zásadě stačí paměť velikosti 400 pozic (400 „šachovnicÿ). (Ano, jedná se o jistý průchod stromem hloubky ≤ 400; přitom není třeba konstruovat v paměti celý strom, ale stačí vždy udržovat aktuální větev.) Tím jsme si připomněli, že i v malém prostoru (malé paměti) se pochopitelně dají provádět časově náročné výpočty. Nadefinovali jsme třídy PSPACE, NPSPACE a připomněli jsme si Savitchovu větu z referátu na cvičení (a z učebního textu), která mj. implikuje PSPACE = NPSPACE. Znázornili jsme si obrázkem inkluze PTIME ⊆ NPTIME ⊆ PSPACE = NPSPACE. Má se obecně zato, že obě inkluze jsou vlastní, byť nikdo nevyvrátil možnost PTIME = PSPACE. Připomněli jsme si, co jsou NP-úplné problémy a nadefinovali jsme PSPACE-úplné problémy. Jako příklady PSPACE-úplných problému jsme uvedli QBF (problém pravdivosti
Teoretická informatika — průběh výuky v semestru
2
kvantifikovaných booleovských formulí), Eq-NFA (ekvivalence nedeterministických konečných automatů) a Eq-RegExp (ekvivalence regulárních výrazů). (Žádnému posluchači samozřejmě nedělá nejmenší problém uvést přesné definice problémů a příklady pozitivních a negativních instancí, že ano.) Uvedli jsme také, že nejrůznější deskové a grafové hry se dají zformalizovat jako PSPACEtěžké (případně PSPACE-úplné) problémy. Např. u šachů by to ovšem chtělo definovat např. (n × n)-šachy (pro všechna n, nejen n = 8). (Připomeňme, že podle našich definic patří každý problém s konečně mnoha instancemi do třídy T (1), tedy má konstantní složitost!) Všimli jsme si, že problém QBF lze definovat jako zjišťování existence vítězné strategie ve hře dvou hráčů, kde Eva („existenční hráčÿ) nasazuje existenčně vázané proměnné a Adam („univerzální hráčÿ) nasazuje univerzálně vázané proměnné. Aproximační algoritmy Přiblížili jsme si elementární základy zachycené v sekci 10.3. Pravděpodobnostní algoritmy Přiblížili jsme si elementární základy zachycené v sekci 10.4. Speciálně jsme se věnovali problému prvočíselnosti. Uvědomili jsme si, že algoritmus Máš-li testovat prvočíselnost zadaného (např. několikasetmístného) k, projdi všechna a, 1 < a < k a zjišťuj, zda Divides(a, k) (tedy zda (k mod a) = 0) . . . je exponenciální (ve velikosti zápisu k). (A to i při přímočarých vylepšeních, při nichž √ zkoumáme jen lichá a ≤ k apod.) Také jsme si všimli, že pravděpodobnostní algoritmus √ Vygeneruj náhodné a (řekněme liché a, 1 < a ≤ k); jestliže Divides(a, k), return NE, jinak return ANO. nám moc nepomůže. Vydá-li (nějaký) jeho běh NE, tak sice víme jistě, že k není prvočíslo, ale vydá-li ANO pro dané k třeba při miliónkrát opakovaném provedení, nemůžeme si vůbec být jisti, že k je prvočíslem. (Např. pro velké číslo m = pq, kde p, q jsou prvočísla, je náhodná trefa jednoho z dělitelů p, q téměř nemožná.) Pak jsme naznačili, že (malá) Fermatova věta, je základem podstatně lepšího algoritmu (k čemuž se ještě vrátíme na cvičení). Sekce pro hlubší zájemce – důkazy Diskutovali jsme jeden pozoruhodný důkaz z oblasti teorie složitosti, který se dá vyjádřit sloganem
Teoretická informatika — průběh výuky v semestru
3
nedeterministický prostor je uzavřený na doplněk. Ukázali jsme ovšem jen následující speciální Tvrzení: Ke každému nedeterministickému Turingovu stroji M s prostorovou složitostí O(n), který rozhoduje problém P , existuje (lze sestrojit) nedeterministický Turingův stroj M ′ rovněž s prostorovou složitostí O(n), který rozhoduje problém P (tedy doplňkový problém problému P ). Jestliže tedy M má pro slovo w alespoň jeden přijímající výpočet, tak všechny výpočty stroje M ′ na w jsou nepřijímající; jestliže všechny výpočty stroje M na w jsou nepřijímající, pak existuje alespoň jeden výpočet M ′ na w, který je přijímající. Toto tvrzení mj. znamená, že třída tzv. kontextových jazyků je uzvařena na doplněk. To byl od 60. let 20. století známý otevřený problém a mezi zainteresovanými převládal názor, že tato třída na doplněk uzavřena není. Tvrzení dokázal jako první student informatiky na MFF UK v Bratislavě R. Szelepcsenyi na jaře 1987. Než ovšem bylo řešení (dopracováno, zobecněno a) oznámeno odborné veřejnosti, přišel nezávisle s řešením známý vědec N. Immerman v USA. Proto se tomuto tvrzení (v obecnější podobě) dnes říká „The Immerman-Szelepcsenyi Theoremÿ. Načrtli jsme si hlavní myšlenku: Má-li M ′ uloženo v čítači c číslo ci udávající počet konfigurací stroje M , do kterých se tento stroj může dostat v i krocích výpočtu na w, pak do čítače c′ spočte ci+1 následovně: Generuje systematicky všechny možné konfigurace C1 , C2 , . . . , Cm stroje M velikosti SM (|w|) (kde SM je prostorová složitost stroje M ); na začátku také vynuluje čítač c′ . Pro každou vygenerovanou Cj zjišťuje, zda Cj může být dosažena v i + 1 krocích takto: Generuje (v jiném kousku paměti) systematicky všechny možné konfigurace D1 , D2 , . . . , Dm stroje M velikosti SM (|w|); na začátku také vynuluje čítač d. Pro každou Dℓ nedeterministicky „hádáÿ, zda Dℓ je dosažitelná v i krocích. Pokud si tipne, že ne, pokračuje vygenerovaním Dℓ+1 . . . Pokud si tipne, že ano, odsimuluje nedeterministicky zvolených i kroků stroje M na w: když takto dosažená konfigurace není totožná s Dℓ , stroj M ′ neúspěšně skončí; když takto dosažená konfigurace je totožná s Dℓ (M ′ tedy ověřil, že Dℓ je dosažitelná v i krocích), M ′ zvýší čítač d o 1 a ověří, zda z Dℓ lze jedním krokem dosáhnout Cj : pokud ano, zvýší čítač c′ a začne zkoumat Cj+1 , pokud ne, pokračuje vygenerováním Dℓ+1 . . . Pokud takto prošel všechny D1 , D2 , . . . , Dm , aniž zjistil, že Cj je dosažitelná v i+1 krocích, tak ověří, zda hodnoty v čítačích c a d jsou stejné: když nejsou, M ′ neúspěšně končí, když jsou (tedy M ′ skutečně správně uhodl a ověřil všechny konfigurace Dℓ , které jsou dosažitelné v i krocích, a takto ověřil, že Cj skutečně není dosažitelná v i + 1 krocích), pokračuje M ′ zkoumáním Cj+1 (aniž zvýšil c′ ) . . . Po (úspěšném) spočtení ci+1 (v čítači c′ ), zkopíruje M ′ hodnotu c′ do čítače c, vynuluje c′ a pustí se do výpočtu ci+2 . . . Toto provádí pro vš. i ≤ m, kde m je počet všech možných konfigurací stroje M velikosti SM (|w|); kontroluje si tento hlavní cyklus speciálním čítačem, pro nějž mu zajisté stačí prostor O(n). Pokud během práce M ′ někdy zjistí, že je dosažitelná nějaká přijímající konfigurace (stroje M při výpočtu na w), M ′ okamžitě skončí neúspěšně
Teoretická informatika — průběh výuky v semestru
4
(tedy nepřijme). Pokud se to nestalo a stroj M ′ prošel (bez neúspěšného ukončení z důvodů popsaných výše) výpočet c1 , c2 , . . . , cm , tak přijme. K ověření korektnosti dodejme: Když M má přijímající výpočet pro w, tak má také přijímající výpočet, v němž se neopakují dosažené konfigurace, a tedy má výpočet délky ≤ m. Poznámka. Detailnější popis důkazu (obecnějšího tvrzení) lze najít např. i v Internetových zdrojích. (Google: Immerman-Szelepcsenyi Theorem.) Partie textu k prostudování Kapitola 9 (speciálně Třída PSPACE). Sekce 10.3. (Aproximační algoritmy). Sekce 10.4. (Pravděpodobnostní algoritmy).
Cvičení Prezentace referátů Referát č. 26 (Problém QBF; Quantified Boolean Formulas) Uvažujme problém Název: QBF (problém pravdivosti kvantifikovaných booleovských formulí) Vstup: formule (∃x1 )(∀x2 )(∃x3 )(∀x4 ) . . . (∃x2n−1 )(∀x2n )F(x1 , x2 , . . . , x2n ), kde F(x1 , x2 , . . . , x2n ) je booleovská formule v konjunktivní normální formě. Otázka: je daná formule pravdivá ? Navrhněte algoritmus, který řeší problém QBF a má prostorovou složitost omezenou polynomem. (Tím ukážete, že QBF je v PSPACE.) Návod. Řekneme, že formule F(x1 , x2 , . . . , x2n ) je OK pro posloupnost booleovských hodnot b1 , b2 , . . . , bi , kde 0 ≤ i ≤ 2n, jestliže buď i = 2n a F(b1 , b2 , . . . , b2n ) = true, nebo i < 2n, i je liché a F je OK jak pro b1 , b2 , . . . , bi , true, tak pro b1 , b2 , . . . , bi , f alse , nebo i < 2n, i je sudé a F je OK pro alespoň jednu z posloupností b1 , b2 , . . . , bi , true a b1 , b2 , . . . , bi , f alse . Ověřte nejprve, že formule (∃x1 )(∀x2 )(∃x3 )(∀x4 ) . . . (∃x2n−1 )(∀x2n )F(x1 , x2 , . . . , x2n ) je pravdivá právě tehdy, když F je OK pro prázdnou posloupnost. Pak sestavte kýžený algoritmus (a prokažte, že jeho prostorová [tedy paměťová] složitost je polynomiální). Referát č. 27 (Oblázková hra v PSPACE) Uvažujme problém, jehož instancí je orientovaný graf s vybraným vrcholem v a dále k ‘oblázků’. Můžeme v jakémkoli pořadí provádět následující elementární kroky:
Teoretická informatika — průběh výuky v semestru
5
• na vrchol x můžeme položit oblázek, pokud v daný okamžik leží oblázky na všech vrcholech, z nichž vede hrana do x, • oblázek položený na vrchol můžeme odebrat (a znovu použít později). Otázkou je, zda existuje posloupnost kroků, při níž položíme oblázek na zadaný vrchol v. Prokažte, že problém je v PSPACE. (Jednou z motivací problému je problém přidělování paměti při výpočtu; stačí daný počet registrů k provedení určeného výpočtu ?) Příklady Příklad 14.1 Připomeňme si (PSPACE-úplný) problém Název: QBF (problém pravdivosti kvantifikovaných booleovských formulí) Vstup: formule (∃x1 )(∀x2 )(∃x3 )(∀x4 ) . . . (∃x2n−1 )(∀x2n )F(x1 , x2 , . . . , x2n ), F(x1 , x2 , . . . , x2n ) je booleovská formule v konjunktivní normální formě.
kde
Otázka: je daná formule pravdivá?
Uveďte nějaké malé, ale netriviální, příklady pozitivních a negativních instancí problému. Pak definujte přesně pravidla hry pro hráče Eva („existenční hráčÿ) a Adam („univerzální hráčÿ) načrtnuté na přednášce. Jde o to, definovat hru tak, aby Eva měla vítěznou strategii (mimochodem, co to je vítězná strategie?) právě tehdy, když je zadaná formule pravdivá (a Adam měl vítěznou strategii právě tehdy, když je zadaná formule nepravdivá). Zbude-li čas, nakonec ilustrujte na malém příkladu, jak lze obecnou plně kvantifikovanou booleovskou formuli φ převést (v polynomiálním čase) na ekvivalentní φ′ , která je ve tvaru požadovaném pro vstup problému QBF. Příklad 14.2 Následující tvrzení je známo jako „Malá Fermatova větaÿ. Tvrzení. Jestliže p je prvočíslo, tak pro každé a, 0 < a < p, platí ap−1 ≡ 1
(mod p)
. (Když p není prvočíslo, tak to neplatí, jak byste se měli být schopni sami snadno přesvědčit [např. zbude-li čas na cvičení]). Přesvěčdte se, že tvrzení platí pro p = 11. Přitom si uvědomte, jak je užitečné tzv. opakované umocňování. Můžete postupovat vyplněním následující tabulky; přitom využijte, že x10 = x8 · x2 , tedy x10 mod 11 = (x8 mod 11) · (x2 mod 11) mod 11.
Teoretická informatika — průběh výuky v semestru x 1 2 3 4 5 6 7 8 9 10
x2 mod 11
x4 mod 11
x8 mod 11
6
x10 mod 11
Pak vyplňte podobnou tabulku pro neprvočíslo 15. x 1 2 3 4 5 6 7 8 9 10 11 12 13 14
x2 mod 15
x4 mod 15
x8 mod 15
x14 mod 15
Uvedená pozorování nabízejí zvážit jistý (polynomiální) pravděpodobnostní algoritmus k testování prvočíselnosti (velkých čísel). Jak vypadá tento algoritmus? (Poznámka. Ten algoritmus „téměřÿ funguje, „ošálíÿ jej ale tzv. Carmichaelova čísla; naprosto korektní pravděpodobnostní algoritmus využívá o něco hlubší poznatky z teorie čísel.)
