#let srep(..body) = $chevron.l #body.pos().join($,$) chevron.r$
#let mprev = $attach(<=, br: m)$
#let mpprev = $attach(<=, br: m, tr: p)$
#let OO = $cal(O)$
#set page(
  paper: "a5"
)
#set text(
  lang: "cs"
)

#let tile(a,b,c,d) = rect(width: 4em, height: 4em, inset: 3pt)[
  #set text(size: .8em)
  #place(line(start: (0% - 3pt, 0% - 3pt), end: (100% + 3pt, 100% + 3pt)))
  #place(line(start: (0% - 3pt, 100% + 3pt), end: (100% + 3pt, 0% - 3pt)))
  #place(top + center, a)
  #place(left + horizon, b)
  #place(right + horizon, c)
  #place(bottom + center, d)
]
= A
== (A1) Riceova věta, důkaz pomocí $m$-převoditelnosti.
- Je-li $cal(C)$ množina PD jazyků, pak jazyk
  $ L_cal(C) = {srep(M) | L(M) in cal(C)} $
  je rozhodnutelný pouze pokud $cal(C) = emptyset$ nebo $cal(C) = "PD"$
- *Dk.*: $L_cal(U) mprev L_cal(C) \/ overline(L_cal(C))$
  - pokud $cal(C)$ neobsahuje prázdný jazyk, převedeme $srep(M,x)$ na TS, který pro vstup $y$ nejdřív zavolá $M(x)$ a pokud přijme, zavolá TS pro nějaký (neprázdný z předpokladu) $L in cal(C)$ na vstup $y$
    - pokud $M$ přijímá $x$, jazykem vytvořeného TS bude $L in cal(C)$
    - pokud $M$ nepřijímá $x$, jazykem vytvořeného TS bude $emptyset in.not cal(C)$
  - pokud $cal(C)$ obsahuje prázdný jazyk, převedeme $srep(M,x)$ na TS, který pro vstup $y$ nejdřív zavolá $M(x)$ a pokud přijme, zavolá TS pro nějaký (neprázdný z předpokladu) $L' in.not cal(C)$ na vstup $y$
    - pokud $M$ přijímá $x$, jazykem vytvořeného TS bude $L' in.not cal(C)$
    - pokud $M$ nepřijímá $x$, jazykem vytvořeného TS bude $emptyset in cal(C)$
== (A2) Savičova věta.
- Pro každou funkci $f(n) >= log_2 n$ platí:
  $ "NSPACE"(f(n)) subset.eq "SPACE"(f^2(n)) $
- *Dk.*:
  - NTS $M$ v $OO(f(n))$ → DTS $M'$ v $OO(f^2(n))$
  - technické předpoklady
    - $M$ má jednostranně nekonečnou pracovní pásku (proč?)
    - $M$ má jednoznačnou přijímací konfiguraci $C_F$
  - $M'$ prohledá všechny konfigurace $M$, než najde cestu z $C_0^x$ do $C_F$
    - celkem $2^(c_M f(n))$ konfigurací
    - rekurzivní rozděl a panuj algoritmus
    - $OO(f(n))$ úrovní rekurze, každá potřebuje $OO(f(n))$ na uložení čísla konfigurace
  - pokud není $f(n)$ vyčíslitelná (nebo potřebuje moc prostoru k vyčíslení)
    - iterace $f(n) = i = 1,2,3...$, dokud není nalezená cesta, nebo není dosažitelná žádná konfigurace, které nestačí prostor
== (A3) Deterministická prostorová hierarchie.
  - *Prostorově konstruovatelná* funkce $f: NN -> NN$, $f(n) >= log_2 n$, která zobrazuje $mono(1)^n$ na $f(n)$ vyčíslitelná v prostoru $OO(f(n))$
  - Pro každou prostorově konstruovatelnou funkci $f$ existuje jazyk A rozhodnutelný v prostoru $OO(f)$ ale ne v $o(f)$.
    - vytvoříme stroj $D$, který pracuje v prostoru $OO(f)$, odsimuluje libovolný stroj v pracující v $o(f)$#footnote[Tedy specificky neodsimuluje sám sebe a tedy může existovat :)] a odpoví opačně
      - kvůli asymptotice uvažujeme řetězce ve tvaru $srep(M)mono("10*")$ (můžeme na konec přidat $mono("10")^(n_0)$, $n_0$ je z definice $o(f)$)
      - při zacyklení rejectneme po $2^(f(n))$ krocích
== (A4) Deterministická časová hierarchie.
  - *Časově konstruovatelná* funkce $f: NN -> NN$, $f(n) in Ω(n log n)$, která zobrazuje $mono(1)^n$ na $f(n)$ vyčíslitelná v čase $OO(f(n))$
  - Pro každou časově konstruovatelnou funkci $f$ existuje jazyk A rozhodnutelný v čase $OO(f)$ ale ne v $o(f/(log f))$.
    - vytvoříme stroj $D$, který pracuje v čase $OO(f)$, odsimuluje libovolný stroj v pracující v $o(f/(log f))$ a odpoví opačně
      - stejný trik s $srep(M)mono("10*")$
      - počítání kroků trvá $Θ(log f)$
      - inicializace čítače na $ceil(f/(log f))$ trvá $OO(f)$
      - stav simulovaného stroje a $srep(M)$ se drží na druhé pásce neustále u hlavy
      - na další pásce počítadlo – posun trvá $Θ(log f)$ na každý krok
== (A5) Cookova-Levinova věta (NP-úplnost SAT)
  - SAT je NP-úplný
  - ukážeme, že $∀A ∈ "NP"$ $A mpprev 🛁 mpprev "SAT"$
  - NP ⇒ NTS přijme v $p(n)$ čase
  - předpoklady:
    - jednoznačný přijímací stav a konfigurace s prázdnou páskou
    - stroj neopouští vymezený prostor velikosti $p(n)$
  - koupelna
    - vysoká a široká $p(n)$
    - horní strana $(q_0, x_1), x_2 ... x_n, λ ... λ $
    - dolní strana $(q_f, λ), λ ... λ$
    - levá i pravá $λ ... λ$
    - kachle:
      - $tile(mono(a), λ, λ, mono(a)) ∀ mono(a) in Σ$

      - $tile((q_i, mono(a)), λ, λ, (q_j, mono(b))) ∀ (q_j,mono(b),N) in δ(q_i, mono(a))$

      - $tile((q_i, mono(a)), λ, q_i_R, mono(b)), tile(mono(c), q_i_R, λ, (q_j, mono(c))) ∀ (q_j,mono(b),R) in δ(q_i, mono(a))$

      - $tile(mono(c), λ, q_i_L, (q_j, mono(c))), tile((q_i, mono(a)), q_i_L, λ , mono(b)) ∀ (q_j,mono(b),L) in δ(q_i, mono(a))$

      - $tile((q_f, λ), λ, λ, (q_f, λ))$
    - kachle → SAT
      - formule pro nejvýše jednu kachli na každém políčku
      - formule pro alespoň jednu kachli na každém políčku
      - formule pro sousedění kachlí vedle sebe
      - formule pro sousedění kachlí nad sebou
      - formule pro levou, pravou, horní a dolní stěnu

= B
== (B1) Univerzální Turingův stroj a nerozhodnutelnost jazyka univerzálního Turingova stroje.
  - kódování pomocí $Γ = {#("01LNR|#;".split("").filter(c => c != "").map(c => $mono(#c)$).join($,$))}$
    - kóduje se celá přechodová funkce :
      - $∀ C in δ: (q,c → q',c',Z)$
      - $(q)_B, (c)_B, (q')_B, (c')_B, Z$
      - $C_1\#C_2...\#C_n$
  - $Γ → {mono(0), mono(1)}^3$
  - ${mono(0), mono(1)}^* → "index"(w)$
  - 3-páskový TS
    + $srep(M, x)$
    + pracovní páska $M$, zakódovaná do ${mono(0), mono(1), mono(|)}$
    + $(q_i)_B$
  - nerozhodnutelnost:
    - $ bold(A)_(i,j) = cases(1 "pokud" w_j in L(M_i), 0 "pokud" w_j in.not L(M_i)) $
    - DIAG = negace diagonály $bold(A)$ ⇒ liší se od každého řádku
== (B2) RAM a ekvivalence s Turingovým strojem.
  - instrukce
    - set reg to constant
    - add
    - sub
    - copy to indirect
    - copy from indirectrandom access stored program
    - jump if not zero
    - read
    - write
  - RASP – Random Access Stored Program (já bych to pojmenoval XRAM – eXecutable RAM 😁)
  - PRAM – Parallel RAM
  - TS → RAM
    - zleva omezená páska
    - triv
  - RAM → TS
    - pásky
      + Vstup
      + Výstup
      + Paměť RAM
        - index | hodnota \# index | hodnota ...
      + Pomocná
== (B3) Vlastnosti (turingovsky) rozhodnutelných a částečně rozhodnutelných jazyků (uzávěrové vlastnosti, Postova věta, enumerátory).
  - PD i DEC jsou uzavřené na $inter$, $union, dot, *$
  - DEC jsou uzavřené na $overline(L)$
  - co-PD := $overline("PD")$
  - Postova věta: $"PD" inter "co-PD" = "DEC"$ (TS pro $L$ a $overline(L)$ paralelně rozhodnou)
  - $L = {x in Σ^* | ∃y∈Σ^* srep(x,y) ∈ B}$
  - PD ⟺ existuje enumerátor
  - DEC ⟺ existuje enumerátor, enumeruje v shortlex
== (B4) Definice základních tříd složitosti a důkaz $"NTIME"(f(n)) ⊆ "SPACE"(f(n))$.
  - pro NTS v NTIME($f$) lze zkonstruovat DTS, který pracuje ve SPACE($f$)
    - iterujeme přes všechny posloupnosti adresy uzlů stromu výpočtu
    - posloupnost je dlouhá max $f$, stroj jako takový nezabere víc než $f$
== (B5) Definice základních tříd složitosti a důkaz věty o vztahu prostoru a času $forall L in "NSPACE"(f(n)) exists c: L in "TIME"(2^(c dot f(n)))$
  - $2^(c dot f(n))$ je počet možných konfigurací, po kterých se původní NTS nutně zacyklí
  - všechny se dají prohledat v $OO(2^(c dot f(n)))$
  - velikost konfigurace nevíme dopředu, můžeme generovat inkrementálně
  - $c$ je různé pro každý stroj, primárně protože velikost abecedy a počet stavů
== (B6) Dvě definice třídy NP a jejich ekvivalence.
  - NTIME($p(n)$)
  - polynomiální verifikátor
  - ⇒ verifikátorem je posloupnost konfigurací
  - ⇐ NTS zapisuje na pásku certifikát
== (B7) Polynomiální převod 3-SAT na Vrcholové pokrytí.
  - dvojičky pro proměnné a trojúhélníky pro klauzule
== (B8) Definice třídy FPT a kernelu a jejich souvislost. Kernelizace Vrcholového pokrytí
  - Problémy řešitelné v $OO(f(k) dot |I|^c)$, pro algoritmicky vyčíslitelnou $f$ a konst. $c$
  - Kernel = problém, jehož velikost závisí už jen na $k$
  - kernelizace VP
    - iterujeme
      + odstraníme izolované vrcholy
      + "před-označíme" všechny vrcholy s $"deg"(v) > k$ (odstraníme je a snížíme $k$)
    - pokud už nelze, buď ($|V| <= k^2 + k$ a $|E| <= k^2$) nebo neexistuje vrcholové pokrytí nejvýš k
== (B9) Definice třídy FPT a parametrizovaný algoritmus pro Vrcholové pokrytí založený na prohledávání s omezenou hloubkou (se složitostí menší než $𝓞^*(2^k)$).
  - vybírám libovolnou hranu, označím jeden nebo druhý konec a rekurzím
== (B10) Třída \#P a \#P-úplnost, důkaz těžkosti počítání cyklů v grafu.
  - \#P převádí přes konstantní orákulum polynom. počtem dotazů for some reason
  - parsimonious převod ("šetřivý", "skrblík") zachovává počet certů
  - zaokrouhlení počtu vrcholů na $2^k$NP ≠ co-NP
  - každou hranu v $G$ nahradíme $m = n log n$ dlohou pomlázkou → $G'$
  - OHK ⇒ počet cyklů alespoň $(2^m)^n = (2^(n log n))^n = n^n^2$
  - !OHK
    - každý cyklus v $G$ je max. $n-1$ dlouhý
    - $G$ obsahuje nejvýš $n^(n-1)$ cyklů
    - počet cyklů nejvýš $(2^m)^(n-1) dot n^(n-1) < n^n^2$
== (B11) Třída co-NP a co-NP-úplnost.
  - $overline("SAT")$ a TAUT
  - převádí se normálně $mpprev$
  - $"P" subset "NP" inter "co-NP"$
== (B12) Pseudonáhodné generátory, jednosměrné funkce a jejich souvislost s kryptografií (symetrické šifrování, bit-commitment).
  - $G : {mono(0), mono(1)}^n → {mono(0), mono(1)}^(cal(l)(n))$
  - $forall n in NN : cal(l)(n) > n$
  - pro kažďý pravděpodobnostní poly alg $cal(A)$ platí, že s delším řetězcem je rozdíl v pravděpodobnosti předpovědi dalšího bitu zanedbatelný
  - závazek s 3n bity, $c = cases(G(y) "pokud" b = 1, G(y) xor r "pokud" b = 0)$
== (B13) Příklad zjemnělé redukce (redukce SETH na OV nebo OV na hledání regulárního výrazu v textu).
  - ne ❤️