Sylabus přednášky Výpočetní složitost

Anotace

První semestr

1. Příklady úloh exponenciální a polynomiální složitosti, základní pojmy a třídy složitosti, metody klasifikace úloh do tříd, zmínka o aplikacích v kryptografii.
2. Měření složitosti:
   • Asymptotická složitost v nejhorším případě jako funkce délky vstupu.
   • Zmínka o větě o exponenciálním zrychlení pro některé úlohy.
   • Podmíněné a nepodmíněné dolní odhady složitosti.
   • Značení O(g), Omega(g), Theta(g).
3. Úlohy TAUT, SAT, klika v grafu, Hamiltonovská kružnice, množinové pokrytí.
4. Příklady převoditelnosti mezi úlohami: klika, vrcholové pokrytí, SAT.
5. Neformální zavedení tříd P, NP, PSPACE, pojem úplnosti ve třídě, strukturální složitost.
6. Poznámka o algoritmech pro úlohu SAT, důkazy nesplnitelnosti formulí typu PHP.
7. Výpočetní modely:
   • Jednopáskový a vícepáskový Turingův stroj, časová a prostorová míra složitosti.
   • RAM s jednotkovou a bitovou mírou složitosti, omezení délky slova.
   • Vzájemné převody mezi jedno a vícepáskovým TS a RAM bez důkazu.
   • Booleovské obvody.
   • Simulace TS pomocí efektivně konstruovatelných obvodů.
   • Třídy DTIME(t(n)), DSPACE(s(n)), P a PSPACE.
8. Typy úloh:
   • Výpočet funkce, rozhodovací úloha, vyhledávací úloha.
   • Reprezentace vstupu jako posloupnost symbolů.
   • Požadavky na kódování vstupu, efektivní kódování.
   • Optimalizační úloha, problém maximální kliky, MAX-SAT.
   • Vzájemné převody mezi výpočtem funkce a rozhodovací úlohou na příkladech: splnitelnost výrokové formule, problém Hamiltonovské kružnice.
   • Obecná věta o převodu mezi výpočtem funkce a rozhodovací úlohou.
9. Třída NP a NP-úplnost
   • Zavedení třídy NP pomocí existenční kvantifikace.
   • Zavedení p-převoditelnosti. Příklad: SAT je p-převoditelný na problém kliky a naopak.
   • Tranzitivita p-převoditelnosti, přenos příslušnosti do třídy P přes p-převoditelnost, definice NP-úplnosti.
   • Cookova věta: 3-SAT je NP-úplný. Důkaz převodem postupně na splnitelnost obvodů, na obecnou úlohu SAT a na 3-SAT.
10. NP-úplnost konkrétních úloh
    • přesné 3-pokrytí
    • problém batohu a půlení
    • klika v grafu, nezávislá množina, vrcholové pokrytí
    • množinové pokrytí
    • Hamiltonovská kružnice
    • NP-těžkost problému obchodního cestujícího (TSP) s trojúhelníkovou nerovností
    • MAX-SAT, MAX-2-SAT
11. Polynomiální algoritmus pro 2-SAT.
12. Polynomiální algoritmus řešení problému batohu ve vztahu k velikosti vstupních čísel.
13. Optimalizační úlohy, aproximační algoritmy a měření jejich přesnosti. Aproximační algoritmy pro problém
    • vrcholového pokrytí (faktor 2),
    • obchodního cestujícího (TSP, faktor 3/2),
    • množinového pokrytí (faktor log m),
14. Třída PSPACE, PSPACE-úplnost, úloha QBF je PSPACE-úplná. Problém hra na grafech je PSPACE-úplný.

Druhý semestr

1. Polynomiální hierarchie.
2. Složitost aproximačních úloh, neaproximovatelnost MAX-SAT, problému kliky.
3. Vzájemné převody mezi jedno a vícepáskovým TS a RAM:
   • Programovací jazyk pro TS. Program bez rekurze v tomto jazyce lze automaticky převést (přeložit) na TS.
   • Vícepáskový TS lze simulovat jednopáskovým v čase O(t^2).
   • Polynomiální simulace TS pomocí RAM a naopak.
4. Neuniformní modely, neuniformní TS (TS s pomocnou funkcí) a jeho ekvivalence obecným obvodům, P/poly, Karp-Liptonova věta.
5. Využití náhodnosti pro demonstraci neizomorfnosti dvou grafů.
6. Pravděpodobnostní test neekvivalence read-once rozhodovacích diagramů (BDD).
7. Pravděpodobnostní TS, BPP, zesilování pravděpodobnosti správného výsledku. BPP \subseteq P/poly, BPP \subseteq \Sigma_2 \cap \Pi_2.
8. Booleovské modely, DNF, CNF, rozhodovací stromy. Porovnání výpočetní síly těchto modelů pomocí odhadů složitosti konkrétních funkcí.