Řešené otázky NTIN090

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

Obsah

pozn. státnicové otázky pro I2/3 jsou označené touto ikonkou: (🎓)

Vyčíslitelnost[editovat | editovat zdroj]

Def. TS, RJ a RSJ. Uzavřenost RJ na doplňky. Postova v. (🎓)[editovat | editovat zdroj]

Definice Turingova stroje, rekurzivního a rekurzivně spočetného jazyka. Uzavřenost rekurzivních jazyků na doplňky. Postova věta.

Zážitky ze zkoušek  
  • stačilo na 1*A4: definice TS, M(w)↓ a M(w)↑, definice RS a RSJ, věty o doplňcích RJ a RSJ (bez dk), postova věta s lehkým důkazem uvedeným zde, bez dalších dotazů


Teze ( Churchova-Turingova (1936) ) Ke každému algoritmu v intuitivním smyslu existuje TS, který jej implementuje.

TS $ M = (Q, ∑, δ, q_0, F) $
TS $ M = (Q, ∑, δ, q_0, F) $
💡 ∀RJ je i RSJ
💡 ∀RJ je i RSJ

Turingův stroj[editovat | editovat zdroj]

  • (k-páskový deterministický) TS je 5-tice: M = (Q, ∑, δ, q0, F)
    • Q je konečná množina stavů (řídící jednotky)
    • ∑ je konečná pásková abeceda
      • obsahuje znak λ pro prázdné políčko
    • $ δ : Q \times ∑^k -> Q \times ∑^k \times \{R, N, L\}^k ∪ \{⊥\} $ je přechodová fce
      • ⊥ je nedefinovaný přechod
    • q0 ∈ Q je počáteční stav
    • F ⊆ Q je množina přijímajících stavů.
  • Konfigurace TS obsahuje:
    • stav řídící jednotky
    • slovo na pásce
      • 💡 (od nejlevějšího neprázdného políčka do nejpravějšího)
    • pozice hlavy na pásce
      • 💡 čtené políčko v rámci slova

výpočet TS[editovat | editovat zdroj]

  • M(w)↓ tj. výpočet konverguje pokud výpočet nad vstupem w skončí
    • TS přijímá slovo w
      • po skončení se nachází v přijímacím stavu
    • TS odmítá slovo w
      • po skončení se NEnachází v přijímacím stavu
  • M(w)↑ tj. výpočet diverguje pokud výpočet nad vstupem w nikdy neskončí
  • fce f turingovsky vyčíslitelná pokud ex. TS který jí počítá (💡 tj. f(x)↓=y)
  • ∀ k-páskový TS se dá převezt na 1-páskový

Rekurzivní a rekurzivně spočetný jazyk[editovat | editovat zdroj]

  • L(M) označíme jazyk slov přijímaných TS M
  • L je rekurzivně spočetný (také částečně rozhodnutelný), pokud ∃TS M t.ž.: L = L(M).
  • L je rekurzivní (také rozhodnutelný), pokud ∃TS M t.ž.: sevždy zastaví a L = L(M)

💡 RSJ je spočetně ⇒ ∀ jazyk není RSJ

Uzavřenost rekurzivních jazyků na doplňky[editovat | editovat zdroj]

  • L je RJ ⇒ L je RJ
  • L i L jsou RSJ ⇒ L je RJ

z toho nám vyjde:

Postova věta[editovat | editovat zdroj]

Věta ( Postova ) L je RJ ⇔ L i L jsou RSJ

Dk (přes oba směry implikace)
⇒ L je RS, pro L vytvořím TS M, L=L(M) který přijme když původní TS (rozhodující RJ L) odmítne a zacyklí se když původní TS přijme
⇐ pustím oba TS a čekám na 1. co se zastaví (jeden se určo zastaví protože jeden přijíma A a druhý A)

GČ, UTS (🎓)[editovat | editovat zdroj]

Gödelovo číslo, univerzální Turingův stroj.

Gödelovo číslo[editovat | editovat zdroj]

  • přiřadí každému symbolu a formuli unikátní přirozené číslo
  • Je-li w_e kod TS M => e je Gödelovo číslo stroje M

💡 1 TS může mít ∞ mnoho bin. řetězců co ho kódují => má i ∞ mnoho GČ

Kódování instrukcí TS M = (Q, ∑, δ, q0, F)
Nejdřív do abecedy Γ = {0, 1, L, N, R, |, #, ; }, pak z abecedy $ Γ $ do binární.
$ Q = \{q_0, q_1, . . . , q_r\} $, r ≥ 1, kde $ q_0 $ označuje počáteční, $ q_1 $ jediný { BÚNO } přijímající stav.
$ Σ = {X_0, X_1, X_2, . . . , X_s}, s ≥ 2 $, $ X_0, X_1, X_2 $ označují postupně symboly $ 0, 1, λ $.
$ (x)_B $ značí binární zápis čísla $ x $.
$ C_n = (i)_B|(j)_B|(k)_B|(l)_B|Z $ je kódem instrunkce $ δ(q_i, X_j) = (q_k, X_l, Z) $, kde $ Z ∈ \{L, N, R\} $ (v abecedě $ Γ $)
$ C_1\#C_2\# . . . \#C_{n−1}\#C_n $ je kódem TS $ M $, jde o konkatenací kódú všech instrukcí TS $ M $ (v abecedě $ Γ $)
Bin. kód $ M $ získáme přes: 0→000, 1→001, L→010, N→011, R→100, |→101, #→110, ; →111.
Bijekce $ 1w = e ∈ N $, určuje pro TS $ M $ s bin kódem $ w $$ e $, pak TS značíme $ M_e $

Univerzální Turingův stroj[editovat | editovat zdroj]

  • Univerzální Turingův stroj U umí simulovat libovolný jiný TS M nad libovolným vstupem w.
  • Vstup: dvojice w;x, kde w je bin kódem TS M, x je vstupní slovo pro M
Simulace: $ U(w; x)↓ ⇔ M(x)↓ $ a $ U(w; x)↓ = M(x)↓ $
  • U(e,w) ≃ M(w), počítá stejnou funkci.
  • Zakódování TS navíc umožní každému TS přiřadit přirozené číslo
  • Svůj kód bude mít i UTS, tedy UTS bude schopen simulovat i sám sebe
  • Pokud se M(w) zacyklí, musí se zacyklit i U(e,w)
  • Simulace: $ U(w; x)↓ ⇔ M(x)↓ $ a $ U(w; x)↓ = M(x)↓ $
  • 3-páskový UTS (💡 technicky jednodušší než 1-páskový a lze převést na 1-páskový): vstupno/výstupní, pracovní, stavová
3-páskový UTS
    • Vstupní páska
      • kód simulovaného stroje M a jeho vstup.
      • oddělovač ’;’ z abecedy Γ.
      • 💡 pouze se čte a na závěr na ni přepíše obsah pásky stroje M po ukončení jeho výpočtu.
    • Pracovní páska M
      • uložení slova z pracovní pásky M
      • Připomeňme si, že páskovou abecedu stroje M jsme nijak neomezovali, její znaky si na tuto zakódujeme v binární abecedě stejně, jako je tomu v kódu přechodové funkce M.
      • Ať b označuje délku nejdelšího zápisu znaku páskové abecedy v kódu w Turingova stroje M (dá se tedy s jistou rezervou říci, že hodnota b odpovídá \lceil log2 |Σ| \rceil, kde Σ je pásková abeceda simulovaného stroje M.
      • Pak tato páska bude rozdělena do bloků délky b oddělených symbolem „|“.
      • Každý blok bude kódovat obsah políčka pracovní pásky stroje M týmž způsobem, jakým je daný znak zakódovaný v kódu w přechodové funkce stroje M, doplněný nulami na začátku na délku b (jde o binárně zapsané číslo symbolu, jehož hodnotu nuly přidané na začátek nemění).
      • Polohu hlavy stroje M si UTS pamatuje polohou hlavy na této pracovní pásce.
    • Stavová páska M
      • stav, v němž se aktuálně stroj M nachází.
      • Stav $ q_i $ stroje M zakódován jako $ (i)_B $
        • 💡 totéž číslo, co lze vyčíst z přechodové funkce M uložené v řetězci w na 1. pásce

Algoritmus UTS[editovat | editovat zdroj]

  1. Init
    • kontrola vstupu: kontrola správnosti vstupní pásky
    • příprava prac.pásky: překódujeme vstup na pracovní pásku, návrat na začátek pásky
    • příprava stav.pásky: na stavovou pásku zapíšeme 0 (💡 binárně zapsané číslo stavu q0)
  2. Simulace
    • simuluj kroky M dokud ex. instrukce pro konfiguraci
  3. Zakončení
    • úklid: přepíše obsah pracovní pásky do abecedy {0,1}
    • konec: přečte stavovou pásku a podle stavu přejde do přijímacího/odmítacícího stavu

Alg. nerozhodnutelné problémy (🎓)[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • (P. Kucera) Alg. nerozhodnutelne problemy - klasika, definice co to je problem, rozdil mezi rekurzivne spocetnym a rekurzivnim, Churchova teze a ekvivalence s TS, dale halting problem + ten snadny dukaz, Riceho veta a jeste jeden dva dalsi problemy jako zajimavost.
  • Způsob zkoušení: Zdá se, že mu jde o témata, které mají praktický dopad (např. halting problem). Ptal se, jestli znám ještě další nerozhodnutelný problém. Dostali jsme se i k Riceově větě, ale bránil mi ji dokazovat, protože to nebylo v otázce. Známku mi neříkal. S Majerechem zkoušeli někoho společně. Uklidňovali ho, že mu chtějí pomoct.
  • Algoritmicky nerozhodnutelne problemy - Zacal sem Church-Turingovou tezi a pojem algoritmus vztahl k TS. Pak sem zadefinoval Rekurzivne spocetne a rekurzivni jazyky. Halting problem, Diagonalni jazyk, Univerzalni jazyk, Postova veta. Pak sem presel od TS k CRF tady sem jako priklad uvedl K a K0, definoval CRF a ORF + intuitivni srovnani s TS U vetsiny veci sem mel i dukazy ( vycislitelnosti sem se bal nejvic z okruhu takze sem to mel celkem nadrceny ). Pak se dvorak ptal jak zjistim ze nejakekj problem je nerozhodnutelny ( aniz by clovek musel furt vymyslet specialni dukazy ) to sem chvili vahal ale pak sem si vzpomel na prevoditelnost Rekurzivnich a rekurzivne spocetnych mnozin pomoci prevodni fce ktera musi byt ORF coz se ukazalo jako spravna odpoved. Posledni sada otazek uz smerovala k tomu co se bude dit kdyz budu mit TS s orakulem, jestli potom budou vsechny problemy budou rozhodnutelne...tady sem nevedel, odpovidal sem hodne diplomaticky ( spravna odpoved je TS s 1 orakulem umi resit nejaky problemy, TS s 2 orakulama umi resit jeste vic problemu atd...ale nikdy nelze pokryt vsechny jazyky ) Jeste dodam ze tohle nakonec Dvorak okomentoval slovy ze je to spis takova zajimavost, nic zasadniho pro statnice.
  • Algoritmicky nerozhodnutelné problémy - Napsal jsem Halting problém + ten jednoduchý důkaz. Dále jsem napsal Riceovu větu a jak souvisí s halting problémem. Nakonec jsem napsal Postův korespondenční problém. To zkoušejícímu stačilo a nebyly žádné další otázky.
  • Halting problém (Kolman) . Tu som zadefinoval TS, spomenul som kódovanie TS (nič konkrétne iba že to je číslo), Postovu vetu a dokázal som, že L HALT nie je rekurzivný, na záver som spomenul, že to isté sa dá urobiť aj cez množiny. Žiadne doplnkové otázky.
  • Co to je rozh. problém, halting problém, že to souvisí s tím, že množina K není rekurzivní, Riceova věta s důkazem.
  • Nerozhodnutelné problémy - Stačilo ukázat, že halting problém + definice co to vůbec je problém. Definoval jsem Postův korespondenční problém, pár doplnění, OK.
  • definice co to je problem, rozdil mezi rekurzivne spocetnym a rekurzivnim, Churchova teze a ekvivalence s TS, dale halting problem + ten snadny dukaz


instance problému - vstup

rozhodovací problém(odpověď typu ano/ne) - jazyk řetězců popisujících pozitivní instance a otázku, zda dané slovo – instance problému – patří do tohoto jazyka (kladná instance daného problému)

Jazyk $ L $ je rekurzivní (také rozhodnutelný), pokud ∃ TS $ M $, který se vždy zastaví a $ L = L(M) $.

$ L_{DIAG} $

Věta ( diagonalizační jazyk ) $ L_{DIAG} = \{w_i ∈ \{0, 1\}^* | w_i ∉ L(M_i) \} $ není RSJ (tedy ani RJ)

Dk (sporem)
Předpokládáme že $ L_{DIAG} $ je RSJ ⇒ ∃ TS M že $ L_{DIAG} = L(M_e) $ z čekož nám vychází ale spor:
$ w_e \in L(M_e) ⇔ w_e ∈ L_{DIAG} ⇔ w_e \notin L(M_e) $, kde první ekvivalence vyplývá z toho, že $ L_{DIAG} = L(M_e) $ a druhá ekvivalence z definice $ L_{DIAG} $

univerzální jazyk[editovat | editovat zdroj]

Věta ( univerzální jazyk ) $ L_u = L(U) $ (kde U je UTS) je RSJ, ale není RJ

Dk (sporem)
To, že $ L_u $ je RSJ jsme ukázali tím, že jsme popsali UTS, který jej přijímá.
Zbývá tedy ukázat, že není rekurzivní. Z Postovy věty stačí dokázat pouze, že $ \overline L_u $ není RSJ.
Sporem nechť $ \overline L_u = L(M) $. Pomocí stroje $ M $ zkonstruujeme stroj $ M’ $, který bude přijímat diagonalizační jazyk $ L_{DIAG} $. Už víme, že $ L_{DIAG} $ není RSJ a dospějeme tím tedy ke sporu.
$ M’ $ dostane na vstupu slovo $ w $ a má rozhodnout, zda $ w ∈ L_{DIAG} $, tedy jestli stroj s kódem $ w $ odmítne slovo $ w $.
$ M’ $ udělá pouze to, že zkontroluje, zda w kóduje Turingův stroj způsobem, jaký jsme popsali při popisu UTS. Pokud $ w $ nekóduje syntakticky správně TS, odpovídá prázdnému TS, který slovo $ w $ určitě nepřijme a $ M’ $ tedy skončí přijetím. V opačném případě připíše $ M’ $ za $ w $ kód $ 111 $ (kód „;“) a za ně okopíruje opět slovo $ w $. Poté $ M’ $ spustí na tomto slově stroj $ M $, pokud $ M $ přijme, přijme i $ M’ $, pokud se $ M $ zastaví a odmítne, odmítne i $ M’ $, pokud se $ M $ nezastaví, nezastaví se ani $ M’ $.
$ M’ $ ale přijímá jazyk $ L_{DIAG} $, protože $ M’(w) $ přijme ⇔ $ w $ je validním kódem TS $ N $ a $ N(w) $ nepřijme, což je ekvivalentní tomu, že $ U(w;w) $ nepřijme a $ M(w; w) $ přijme. Fakt, že $ L(M’) = L_{DIAG} $, je však ve sporu s tím, že $ L_{DIAG} $ není RSJ.

problém zastavení[editovat | editovat zdroj]

Věta ( problém zastavení ) $ L_{HALT} = \{w; x |~ w~ kóduje~ TS~ M~ a~ M(x)↓\} $ je RSJ, ale není RJ

Dk
sporem mejme f(x,y) ktera dobehne prave kdyz F(x,y) se zacykli; vezmeme kod f=e a pustme f(e,e) - kdyz dobehne, mela se F(e,e) zacyklit, a kdyz nedobehne, mela F(e,e) dobehnout, ale F je univ. funkce => spor
Dk (sporem)
Že $ L_{HALT} $ je RSJ je zřejmé z existence UTS. $ w;x \in L_{HALT} \Leftrightarrow U(w;x)↓ $
Diagonalizací ukážeme, že $ \overline L_{HALT} $ není RSJ, čímž bude důkaz dokončen díky Postové větě.
Předpokládejme pro spor, že ∃ TS $ M $, že $ \overline L_{HALT} = L(M) $.
Nyní definujme jazyk $ L = \{w_i \in \{0, 1\}^*| M_i(w_i)↑\} $, jde vlastně o diagonálu $ \overline L_{HALT} $. S pomocí TS $ M $ sestrojíme nyní TS $ M_e $ přijímající jazyk $ L $.
Pokud $ M(w_i;w_i) $ přijme, pak přijme i $ M_e(w_i) $, v opačném případě $ M_e(w_i)↑ $. To učiní i v případě, zjistí-li, že $ w_i $ nekóduje syntakticky správně TS a odpovídá tedy prázdnému TS (to je zde nutné odlišit jen proto, že kdyby $ w_i $ obsahovalo oddělovač „;“, pak by $ w_i;w_i $ mohlo odpovídat výpočtu jiného TS nad jiným vstupem).
TS $ M_e $ přijme svůj vstup ⇔ $ M_e↓ $. Zřejmě platí, že $ L(M_e) = L $.
Nyní se podívejme, jestli $ w_e \in L $ ($ w_e $ je kód $ M_e $):
  1. Pokud $ w_e ∈ L $, znamená to, že se $ M_e(w_e) $ zastaví a přijme, protože $ L = L(M_e) $, to ale současně znamená, že $ M_e(w_e)↑ $ podle definice $ L $, což je pochopitelně ve sporu.
  2. Nyní předpokládejme, že $ w_e \notin L $, ale podle definice $ L $ to znamená, že $ M_e(w_e)↓ $. Z toho jsme dostali $ w_e ∈ L(M_e) = L $, což je však ve sporu s předpokladem.
Jazyk $ L $ použitý v důkazu není nic jiného než $ L_{DIAG} $, pokud bychom předpokládali, že TS přijímají zastavením v jakémkoli stavu.

PRF, ČRF, RP, RSP a vlast. (🎓)[editovat | editovat zdroj]

Definice primitivně a částečně rekurzivních funkcí, rekurzivních a rekurzivně spočetných predikátů. Jejich základní vlastnosti - podmíněný příkaz, omezená minimalizace, uzavřenost na aritmetické operace, (ne)uzavřenost na logické spojky a kvantifikátory (omezené i neomezené).

Zážitky ze zkoušek  
  • Surynek - Základní definice, funkci x+y definovat jako ČRF, detaily ostrých inkluzí PRF/ORF/ČRF. Otázka: Je univerzální funkce pro třídu PRF také PRF? Ne, dokonce není ani ORF, protože nemůže být totální.


PRF⊂ORF⊂ČRF
funkce predikát množina problém
částečně rekurzivní /
rekurzivně spočetný
ČRF RSP RSM částečně rozhodnutelný
obecně rekurzivní ORF ORP rekurzivní množina rozhodnutelný
primitivně rekurzivní PRF PRP nezavádí se nezavádí se

podmíněná rovnost $ f(x_1,..,x_n) \mathbf{≃} g(x_1,..,x_n) $ znamená: hodnota $ f(x_1,..,x_n) $ je definována ⇔ definována i hodnota $ g(x_1,..,x_n) $, a pak jsou si také rovny

minimalizace $ M_n(f) = h $
  • h nabývá nejmenší hodnoty y, pro níž je f definováno a rovno 0. Navíc pro všechny hodnoty nižší než y musí být hodnota f definována.
  • Poslední proměnná ve funkci f má zvláštní význam. Snažíme se ji minimalizovat, to jest najít nejmenší y takové, aby f vracela nulu.
  • Pokud se jako f předá funkce, která nikdy nevrací nulu, tak operátor minimalizace vytvoří funkci, která nebude nikde definovaná
(výše uvedený pseudokód se zacyklí). To se u předchozích operátorů stát nemohlo: pokud dostaly na vstupu všude def. fce, vrátily také všude def. funkci.
  • Pokud nechceme zavádět nulární funkce, je nutné definici operátoru minimalizace doplnit o podmínku, že f je funkce alespoň dvou proměnných.
  • Místo $ ↓= $ (zkratka za konverguje a rovná se) bychom v definici klidně mohli psát jen $ = $. Použití $ ↓≠ $
(zkratka za konverguje a nerovná se) je ale důležité, například pokud $ f(x_1,...,x_n,0)↑ $, tak $ h(x_1,...,x_n) $ také není definováno,
i kdyby třeba $ f(x_1,...,x_n,1)=0 $.

Základní funkce:

  • nulová (konstantní) funkce $ o(x) = 0 $
  • následník $ s(x) = x + 1 $
  • projekce $ I^j_n (x_1, .., x_j, .. , x_n) = x_j (∀j,n: 1 ≤ j ≤ n) $ (💡 vrací hodnotu j-tého parametru)

Operátory:

  • substituce $ S^m_n(f,g_1,...,g_m) = h $ kde: $ h(x_1,...,x_n) ≃ f(g_1(x_1,...,x_n),...,g_m(x_1,...,x_n)) $
    • 💡 $ f $$ m $ proměnných a $ g_1, .. , g_m $ $ n $ proměnných
    • 💡 Operátor substituce je základní prvek programování — jednoduše úlohu, kterou mám řešit, vyřeším pomocí funkcí, které už naprogramoval někdo dřív.
  • primitivní rekurze $ R_n(f,g) = h $
    • kde: $ h(0, x_2, ..., x_n) ≃ f(x_2, ..., x_n) $
      $ h(i+1, x-2, ..., x_n) ≃ g(i, h(i,x_2,...,x_n), x_2,..., x_n) $
    • 💡 f je fce n-1 proměnných a fce g n+1 proměnných (n ≥ 2)
    • 💡 operátor primitivní rekurze má sílu for-cyklu.
    • 💡 Proměnná x1 má zvláštní význam — slouží jako čítač
  • minimalizace $ M_n(f) = h $ (má sílu while-cyklu)
$ \mathbf{h}(x_1,...,x_n)\downarrow ≃ min \{ y|\mathbf{f}(x_1,...,x_n,y)\downarrow = 0 \quad a \quad \forall z< y: \mathbf{f}(x_1,...,x_n,z)\downarrow \ne 0\} $
  • μy[P(x,y)]- fce μ vrátí nejmenší y takové, aby platil predikát P(x,y)
    • Lze jí sestrojit pomocí operátoru minimalizace

PRF ⇐ lze odvodit ze 3 základních fcí a pomocí 2 op. substituce a prim. rekurze (NE minimalizace)

  • 💡 všude definována (=totální) - for-cykly (vždy konvergují)
  • 💡 PRF je ORF bez minimalizace

PRP (ORP) ⇐ ∃ pro něj PRF (ORF) charakteristická funkce

  • predikát $ R(x_1,...,x_n) $ je relace nebo libovolný fakt o n proměnných
  • charakteristická fce predikátu R je $ \chi_P(x_1,\dots,x_n)\simeq \begin{cases}1 \quad & \mbox{ pokud } R(x_1,\dots,x_n) \\ 0 \quad & \mbox{ jinak }\end{cases} $
    • 💡 char. fce je ORF
  • 💡 (Obecně) PRM je unární (obecně) PRP.

ČRF (partial μ-recursive functions) ⇐ lze odvodit ze 3 základních funkcí pomocí 3 operátorů (💡 mají navíc while-cyklus ⇒ divergence)

  • ORF - je ČRF def. pro ∀ vstupy (totální)

RSP ⇐ ∃ pro něj ČRF charakteristická funkce

  • částečná char. fce (=ČRF) predikátu $ R $ je funkce $ f_R : N^n → N $: $ f_R(x_1, . . . , x_n)↓ ⇔ R(x_1, . . . , x_n), ∀(x_1, . . . , x_n) ∈ N $.
  • 💡 je def.oborem nějaké ČRF

Jejich základní vlastnosti[editovat | editovat zdroj]

  • uzavřenost na aritmetické operace
    • (konečný součet a součin) f je PRF 2 proměnných ⇒ je PRF:
      • $ g(z, x)=\sum_{y<z}f(y, x) $ (přičemž $ g(0, x)=0 $)
      • $ h(z,x)=\prod_{y<z}f(y, x) $ (přičemž $ h(0, x)=1 $)
    • (důsledek) f je PRF 1 proměnné ⇒ je PRF:
      • $ g(z)=\sum_{y<z}f(y) $ (přičemž $ g(0)=0 $)
      • $ h(z)=\prod_{y<z}f(y) $ (přičemž $ h(0)=1 $)
  • (podmíněný příkaz) - analogie switch/case/if-then
    • $ g_1(x), \dots, g_n(x) $, $ n>0 $ jsou PRF a $ R_1(x), \dots, R_n(x) $ jsou PRP a $ \forall x\in{\mathbb N} $ je splněn !1 z nich.
    • ⇒ tato fce $ f $ je PRF: $ \begin{align} f(x)=g_1(x)&\Leftrightarrow R_1(x)\\ f(x)=g_2(x)&\Leftrightarrow R_2(x)\\ &\vdots&\\ f(x)=g_n(x)&\Leftrightarrow R_n(x) \end{align} $
  • kvantifikátory (omezené i neomezené).
    • (omezená kvantifikace) $ P $ binární PRP ⇒ $ V_P(z, x)=(\forall y<z)[P(y, x)] $ a $ E_P(z, x)=(\exists y<z)[P(y, x)] $ jsou PRP.
    • (neomezená kvantifikace): P unární PRP⇒ (∃y)[P(y)] je RSP a (∀y)[P(y)] je doplněk RSP (∃y)[¬P (y)].
  • (ne)uzavřenost na logické spojky
    • (logické spojky)
    $ P $ a $ R $ unární PRP ⇒ $ R\wedge P $, $ R\vee P $ a $ \neg P $ jsou PRP
    • (konečná konjunkce a disjunkce)
    $ P $ binární PRP ⇒ $ A(x, z)=\bigwedge_{y<z}P(x, y) $ a $ B(x, z)=\bigvee_{y<z}P(x, y) $ jsou PRP
  • (omezená minimalizace)
    $ P $ binární PRP ⇒ tato $ f $ je PRF:
    $ f(x, z)= \begin{cases} \min\{y<z\;|\;P(x, y)\} \quad &\mbox{pokud takové y existuje}\\ z \quad &\mbox{jinak.} \end{cases} $
    Funkci $ f $ budeme také označovat pomocí $ f(x, z)=\mu y<z[P(x, y)] $.

ČRF ⇔ TS, Kleene, UČRF, s-m-n (🎓)[editovat | editovat zdroj]

Ekvivalence ČRF a Turingových strojů (na vyšší úrovni). Kleenova věta o normální formě (bez převodu ČRF na TS), univerzální ČRF, s-m-n věta.


Zážitky ze zkoušek  
  • Tu ekvivalenci jsem napsal jen v bodech (stylem „zakóduju výpočet TS do stringu“, „sestavím predikát, který kontroluje, zda výpočet TS je korektní“, atd., fakt hodně po povrchu), rozepsal jsem jen to, jak se pomocí TS implementuje substituce, a taky mu to celkem stačilo (měl jsem v plánu toho napsat mnohem víc, tohle byl jen takovej začátek), jen se ptal, jak se něco udělá (nevím už přesně co, něco jako jak se překóduje string do binární reprezentace a zpátky, nevím jestli v TS nebo ČRF), tak jsme to společně nějak vymysleli, a dobrý.
  • (Loebl) - Ekvivalence ruznych definic algoritmicky vycislitelnych funkci - Moc jsem nevedel, co presne u tehle otazky bude chtit videt (jasne, Churchova teze, kterou jsem mimochodem nezformuloval tak uplne ciste spravne, ale dal?:) a tak jsem tam naflakal vsechno - CRF, ORF, PRF, RM, RSM, RSP, ORP, jazyky, DTS, NTS - CRF jsem odvodil ze zakladnich funkci pomoci operatoru, ukazal jsem inkluzi s ORF a PRF, naznacil jsem, jak si odpovidaji CRF a NTS a RSM, ORF a DTS a RM. Loebl byl velmi prijemny, prosel si to, chvili dumal nad tim, co se mnou (asi to nebylo uplne ono co chtel videt), rekl, ze tomu zjevne asi rozumim, ale, ze mu chybi nejake prakticke priklady a konkretni formalni prevody mezi vyjadrenimi a pak mi rekl, at mu tedy napisu jeste neco o UTS, pokud o nem neco vim. Nacrtnul jsem tu ctyrpaskovou konstrukci a kodovani UTS, ani jsem to nedopsal a rekl, ze staci.
  • Majerech, Algoritimicky vycislitelne funkce, definice, vlastnosti. Pana Majerecha jsem se bal, ale nakonec byl opravdu hodny! Zdalo se mi, ze poznal, ze tomu clovek rozumi, par otazek a dal se jiz na nic neptal. Napsal jsem definice pres funkce/operatory, pres TS, dale pak mnoziny/predikaty/jazyky. Inkluze + co za funkce jsou, aby to nebylo ostre [bez definovani], par otazek na overeni, ze tomu rozumim a vse ok. Zadne detaily ci Velmi prijemne zkouseni. Behem zkouseni si k nam prisedl i Martin Mares, ktereho to evidentne bavilo a dokonce mi i jednou napovedel :-) Znamka: 1
  • Loebl (SV) -- Algoritmicky vyčíslitelné funkce, jejich vlastnosti, ekvivalence jejich různých matematických definic. Částečně rekurzivní funkce. - Churchova-Turingova teze. Definoval jsem TS a popsal, jak počítá. Rekurzivně spočetné/rekurzivní jazyky. Postova věta. Definice PRF, ORF, ČRF (a predikáty) - zmínit, jakým programovacím konstruktům odpovídají odvozovací fce. Základní lemmata (konečný součet, popis ekvivalentní fce pro switch, atd.). Nakonec bez důkazu, že ČRF a TS jsou ekvivalentně silné. Ptal se na existenci UTS (stačila idea). Vše jsem měl přesně, takže řekl, že mu to stačí na 1.

otázky: vyšší úroveň? , bez převodu ČRF na TS? , smn důkaz? jak se něco udělá (nevím už přesně co, něco jako jak se překóduje string do binární reprezentace a zpátky, nevím jestli v TS nebo ČRF)

💡 efektivně vyčíslitelné = turingovsky vyčíslitelné = algoritmicky vyčíslitelné = algoritmicky řešitelné

Ekvivalence ČRF a TS (na vyšší úrovni)[editovat | editovat zdroj]

Věta ( ČRF ⇒ TS ) $ h $ je ČRF $ n $ proměnných ⇒ $ h $ je Turingovsky vyčíslitelná

💡 Přesněji, existuje Turingův stroj $ M_h $ takový, že pro každou $ n $-tici přirozených čísel $ x_1, x_2, \dots, x_n $ platí
$ M_h((x_1)_B\#(x_2)_B\#\dots\# (x_n)_B)\downarrow\Leftrightarrow h(x_1, x_2, \dots, x_n)\downarrow $
a platí-li $ h(x_1, x_2, \dots, x_n)\downarrow=y $, potom výpočet Turingova stroje $ M_h $ vydá na výstupu řetězec $ (y)_B $.
Dk (konstrukcí TS, zde komplet včetně nižší úrovně)
definujeme TS pro základní funkce a operátory pro odvození $ h $:
  • Základní fce (nulová, následník, projekce) implementuji (vyčíslím) pomocí TS
  • Operátory simuluji na 3 pásk. TS: substituci, primitivní rekurzi jako for-cyklus (počítadlem cyklů), minimalizaci jako while-cyklus (taky počítadlem cyklů)

Věta ( 💡 ) Převod je navíc možno učinit efektivně. Jinými slovy, existuje Turingův stroj CRF2TS, který pokud na vstupu dostane kód ČRF $ h $, spočítá Gödelovo číslo $ e $ stroje $ M_e $, který počítá funkci $ h $.


Věta ( TS ⇒ ČRF ) funkce $ f $ turingovsky vyčíslitelná ⇒ je $ f $ ČRF

Dk (jeden krok TS je PR - omezené cykly, TS pracuje, dokud neskončí = while-cyklus (tj. minimalizace), tedy program = minimalizace čehosi, kde to cosi už je PR)
  • předpoklady: f je def. jako tur. vyčíslitelná ⇒ ∃ TS $ M_e $ co jí počítá (💡 to je z definice tur.vyčíslitelnosti)
  • zakóduju výpočet (tj: posloupnost konfigurací Ki) TS do stringu: K1;...;Kt
Tato část je neúplná a potřebuje rozšířit. jak se to dělá?
  • sestavím PRP T(g.č.TS, x, g.č.kódu výpočtu TS), který kontroluje, zda daný řetězec kódu TS kóduje výpočet TS nad vstupem x
  • na predikát pustím minimalizaci y ($ \mu y[T(e, x, y)] $)
  • pomocí fce $ \cal U $ z ní vytáhnu g.číslo poslední konfigurace
  • tedy $ f(x)=\cal U(\mu y[T(e, x, y)]) $
💡 U je zřejmě PRF

Kleenova věta o n.f. (bez převodu ČRF na TS)[editovat | editovat zdroj]

$ \mathbf{ \varphi_e^{(n)}} $ je ČRF $ n $ proměnných, kterou počítá stroj $ M_e $

Věta ( Kleenova věta o normální formě ) $ \exists PRF \quad \cal U(y) $ a PRP $ T_n(e, x_1, \dots, x_n, y) $, pro které platí: $ (\forall n\in\mathbb N) (\forall e\in{\mathbb N})\; \varphi_e^{(n)}(x_1, \dots, x_n) \simeq\cal U(\mu y[T_n(e, x_1, \dots, x_n, y)]) $

💡 neboli, každý program se dá zjednodušit na 1 while cyklus :)

Dk
podle důkazu TS ⇒ ČRF

Věta ( důsledek Kleeneho věty ) $ R $ je RSP $ \Leftrightarrow \exists $ PRP $ P $ tak, že: $ R(x_1, \dots, x_n)\Leftrightarrow(\exists y)[P(x_1, \dots, x_n, y)] $

💡 RP jsou ty, které jsou algoritmicky rozhodnutelné, RSP jsou ty, které jsou algoritmicky ověřitelné, podá-li nám někdo certifikát (tedy $ y $) dokazující jejich platnost. Tedy u RSP nejsme sice obecně schopni efektivně rozhodnout, jestli platí, ale pokud platí a někdo nám dá svědka $ y $ stvrzující tento fakt, jsme schopni efektivně ověřit, že jde skutečně o certifikát platnosti.

univerzální ČRF[editovat | editovat zdroj]

Věta ( O univerzální funkci ) $ \forall $ třídu proměnných $ n>0 $ $ \exists $ univerzální ČRF: $ \varphi_z^{(n+1)}(e, x_1, \dots, x_n) $ taková, že $ \varphi_z^{(n+1)}(e, x_1, \dots, x_n)=\varphi_e^{(n)}(x_1, \dots, x_n) $ (tedy vyčísluje e-tou funkci)

💡 existuje i univerzální funkce, a to pro každou třídu $ n $ proměnných (takže ta univerzální funkce pak dostane těch $ n $ proměnných + číslo funkce, kterou má emulovat, a udělá to), přičemž je docela pěkná (je ve tvaru minimalizace PRP)

Dk(podle Kleeneovy)
$ \varphi_z^{(n+1)}(e, x_1, \dots, x_n) \simeq \cal{U}(\mu y[T_n(e, x_1, \dots, x_n, y)]) $
💡 Nicméně vzhledem k ekvivalenci ČRF a TS bychom také mohli vzít již zkonstruovaný univerzální TS a jemu odpovídající ČRF.

snm věta[editovat | editovat zdroj]

$ \mathbf{ \varphi_e^{(n)}} $ je ČRF $ n $ proměnných, kterou počítá stroj $ M_e $

Churchovo $ \lambda $-značení . Je-li $ V $ výraz, pak pomocí $ \lambda_{ x_1x_2...x_n}V $ označíme funkci na proměnných $ x_1, x_2, \dots, x_n $, která je daná výrazem $ V $.

Věta ( snm ) $ \forall $ m,n > 0 $ \exists $ prostá PRF $ s_n^m $ a $ \forall x, y_1, \dots, y_m $ platí: $ \varphi^{(n)}_{s_n^m(x,y_1,.., y_m)} = \lambda z_1..z_n[\varphi_x^{(m+n)}(y_1, .., y_m, z_1, .., z_n)] $

příklad použití $ s_n^m $ věty
💡  říká, že pokud v naší univerzální funkci, která má $ m+n $ sadu argumentů (jedním z nich je číslo programu, který má běžet),
$ m $ argumentů (+ číslo programu) zafixujeme,
dostaneme funkci zbytku ($ n $) těch argumentů,
a tato fixovací funkce bude hezká (prostá PRF).
Dk (program $ s=s_n^m(x, y_1, \dots, y_m) $, na vstupu dostane z-ka a pak pustí TS $ M_x $ na vstup y-nek a z-tek)
Neformálně popíšeme, co bude dělá program $ s=s_n^m(x, y_1, \dots, y_m) $:
Na vstupu dostane čísla $ z_1, . . . , z_n $, poté spustí stroj $ M_x $ na vstup $ y_1, . . . , y_m, z_1, z_2, . . . , z_n $,
💡 Všechna tato čísla zná, jelikož je buď dostane na vstupu $ M_s $ (v případě $ z_1, . . . , z_n $), nebo je má zakódované do své přechodové funkce jako parametry (v případě $ x, y_1, \dots, y_m $).
💡 Pro tuto úpravu není vůbec rozhodující, jak vypadají instrukce $ M_x $, ani to, jak bude probíhat jeho výpočet, jediné, co je v $ M_x $ třeba změnit jsou čísla stavů tak, aby nekolidovala s nově přidanými stavy.
  • Úprava přechodové funkce $ M_x $ je jednoduchá a vystačí si s PR prostředky $ s_n^m $ je PRF.
  • Kód nového stroje obsahuje nějakým způsobem i hodnoty parametrů fce $ s_n^m $, pro různé hodnoty těchto parametrů budou i různé výstupní hodnoty $ s_n^m $ je prostá.

další zdroje[editovat | editovat zdroj]

Základní vlast. RM a RSM. (🎓)[editovat | editovat zdroj]

Základní vlastnosti rekurzivních a rekurzivně spočetných množin. (Ne)uzavřenost na sjednocení, průnik a doplněk. Postova věta v kontextu množin. Existenční kvantifikátor a výběrová funkce.

Zážitky ze zkoušek  
  • (inicialy JM... zeby Mlcek?) - Rekurzivne funkcie a rekurzivne spocetne mnoziny (nie je to priamo otazka z poziadavkov, nejak som mal proste rozpravat o danej teme), uz pri zadavani mi vravel, ze si mam pripravit vela prikladov, na co je to dobre. Zadefinoval som elementarne funkcie a operatory, vyznam operatorov(for, while), PRF,ORF,CRF, inkluzie a priklady funkcii, kvoli ktorym su inkluzie ostre, definoval som rekurzivne a r.spocetne mnoziny a uviedol som tam znenie tej dlhej vety o vlastnostiach r.s. mnozin. Na zaver som pridal nieco o halting probleme ako priklad vyuzitia celej tej teorie. Skusajuci si to pozrel, nemal nejake pripomienky a zacal sa pytat na tie priklady, tak som povedal ten halting problem, ekvivalenciu programov a este sa pytal, ci existuje funkcia, ktora nie je ani CRF - to som nejak previedol na TS a povedal, ze napriklad diagonalizacny jazyk. Toto mu stacilo, bolo to celkom v pohode.
  • RS a RSM mnoziny, prevoditelnosti - pri zadani spominal aj simple a kreativne, ale nastastie sme sa az tam nedostali, to som sa uz neucil. Definicia zakladnych fcii, operatorov, definicia RS RSM mnozin, potom ze to je ekvivalentne s generovanim pomocou oborov hodnot, tie vety o vztahu rng a RSM, vzdy sa opytal aj na myslienku dokazu. Postova veta (tam sa mu viac pacila odpoved 'pustime dva programy a cakame, ktory skor zastane' nez ten predikat, ktoreho potom selektor je char fciou), potom som zadefinoval 1- a m-prevoditelnost, 1-uplnost, dokazal, ze K je 1-uplna, napisal halting problem a Kryl odchadzal spokojny.
  • Majerech - CRF + RM + RSM - tady jsem kliku, ze jsem si vylosoval zrovna toto, ptz jinak bych tam mohl u Majerecha sedet doted.:) Vypsal jsem vsechny ty definice, nejdulezitejsi vety (Postovu jsem si dovolil i dokazat, coz je u me velmi nezvykle) a ruzna tvrzeni okolo, na ktere jsem si vzpomnel. Ptal se na usekovou fci a generovani bodu - to jsem tapal a radsi hned rekl, ze nevim (jak toto muze byt nekdy osvobozujici:) a zlehka nejake uzaverove vlastnosti. 1-
  • Napsal jsem:
    • definice RM, RSM vč. definice ORF a ČRF (s drobnou chybou – dal jsem dohromady prvky a operátory nad funkcemi),
    • generování (tři věty o oborech hodnot) (Tady se mě ptal, jak fungují ty programy pomocí kterých množiny generuji. Neměl jsem to rozmyšlené, takže to ze mě musel tahat a část říct),
    • 1-převoditelnost, 1-úplnost, K je 1-úplná. Ptal se mě, k čemu ta 1-převoditelnost je. Dával mi návodné otázky a potom jsem si končeně vzpomněl, že asi myslí to, že můžu převést jednu množinu na druhou. Jen tak mimochodem se ptal, kolik je RM a kolik RSM.
    • Všechno jsem psal bez důkazu a nechyběly mu. Nakonec mi řekl, že to mám tak za 1− a jestli chci čistou 1, tak ať mu formálně dokážu, že K je 1-úplná. Řekl jsem mu, že o 1 mi až tak nejde.

charakteristická funkce $ χ_A(x) $ -- charakteristická fce predikátu náležení do množiny ($ χ_A(x) = \downarrow 1 $ pro $ x\in A $ a $ χ_A(x) \downarrow = 0 $ pro $ x\notin A $) $ χ_A(x_1,\dots,x_n)\simeq \begin{cases}1 \quad & \mbox{ pokud } R(x_1,\dots,x_n) \\ 0 \quad & \mbox{ jinak }\end{cases}\,\! $

💡 částečná charakteristická funkce množiny -- $ χ_A(x) = \downarrow 1 $ pro $ x \in A $ a $ χ_A(x)\uparrow $ pro $ x \notin A $

$ dom\,\! $ značí definiční obor, $ rng\,\! $ obor hodnot


RM A ⊆ ℕ ⇐ je-li def. oborem ORF

💡 také nazýváme jako unární RP (příklad: binarni predikat je mnozina dvojic, ale unarni predikat je mnozina prvku)
💡 tj.: char.fce $ χ_A(x) $ je ORF


RSM A ⊆ ℕ ⇐ je-li def. oborem ČRF

💡 také nazýváme jako unární RSP
💡 tj: A = dom ČRF f = {x | f(x)↓}
e-tá RSM $ \mathbf{W_e} = dom~ φ_e = \{ x | φ_e(x)↓ \} $
Pomocí $ \varphi^{(n)}_{e, s} $, kde $ e, n,s\in{\mathbb N} $ označíme konečnou aproximaci $ \varphi_{e, s}^{(n)} $ funkce $ \varphi_e^{(n)} $, kterou definujeme následujícím způsobem:
$ \varphi^{(n)}_{e, s}(x_1, \dots, x_n)\simeq \begin{cases} \varphi^{(n)}_e(x_1, \dots, x_n) \quad & \mbox{pokud }(\exists y<s)[T_n(e, x_1, \dots, x_n, y)]\\ \uparrow\quad & jinak \end{cases} $
rekurzivní konečná aproximace $ \mathbf{W_{e,s}} = dom φ_{e,s} = \{ x | φ_{e,s}(x)↓ \} $

Lemma Predikát $ H $ definovaný jako $ H (e, s, x_1, . . , x_n) ⇔ φ_{e,s}(n)(x_1, . . , x_n)↓ $ je PRP a platí, že: $ φ_e(n) (x_1, . . . , x_n)↓⇔ (∃s)[ φ_{e,s}(n) (x_1, . . , x_n)↓] $ . (v dk předpokladáme, že $ T_n $ z Kleenovy věty je PRP a omezená kvantifikace je PR.)

Věta ( RM - uzavřenost na ∪, ∩ a doplňek ) RM jsou uzavřeny na sjednocení, průnik a operaci doplňku

Dk

předpokládáme, že signum, součet, součin a opatrné odčítání 1 (predecessor) jsou PRF/ORF :

$ A∪B=\{x|[χ_a(x)∨χ_b(x)]\} $
$ A∩B=\{x|[sign(χ_a(x)+χ_b(x))]\} $
$ \overline A=\{x|[1\dot{-}χ_a(x)]\} $
💡 tj: Ten samý jako pri logických operacích pro PRP, jenomže pro unární ORP (rekurzivní množiny). Platí: χA ∩ B(x) = χA(x).χB(x), χP ∩ R(x) = sign(χA(x) + χB(x)), χA(x) = 1 −• χA(x).

Věta ( RSM - uzavřenost na ∪, ∩ ale NE na doplňek ) Rekurzivně spočetné množiny jsou efektivně uzavřené na sjednocení a průnik, nikoliv na průnik.

Dk
A∪B - pustíme oba TS současně a když 1 skončí vstup patří do sjednocení
A∩B - čekám na zastavení obou
💡 tj: Uvažme nejprve sjednocení a funkci f(x, y). Nechť e-tý program počítá následovně. Pro daný vstup x, y, u hledej nejmenší limit s, který již stačí, aby u patřilo do Wx,s nebo do Wy,s. Tedy φe(x, y, u) ≃ μs[u ∈ Wx,s ∨ u ∈ Wy,s]. Z vlastností konečných aproximací, vyplývá, že predikát použitý jako podmínka minimalizace je PRP. Platí tedy, že φe(x, y, u)↓ ⇔ u ∈ Wx ∪ Wy. Program s číslem e je konkrétní program, který sestrojíme s pomocí univerzální ČRF. Funkci f dostaneme pomocí s-m-n věty jako $ f(x, y) = s_1^2(e, x, y) $. Podobně můžeme postupovat i v případě průniku a funkce g, stačilo by místo disjunkce použít konjunkci.

Věta ( Postova věta v kontextu množin ) $ A $ je RM $ \Leftrightarrow A $ i $ \overline A={\mathbb N}\setminus A $ jsou RSM

Dk
⇒ A je RM: A = dom μy[(λxy[1 ∸ χA(x)])≃0]
A' je RSM: A = dom μy[(λxy[χA(x)])≃0]
⇐ paralelni beh obou char. funkci, jedna dobehne
μs[x∈Wi,s ∨ x∈Wj,s]

Kódování uspořádaných dvojic, n-tic:

  • $ ⟨x, y⟩_2 $ je kód uspořádané dvojice [x, y] daný: $ ⟨x, y⟩_2 = (x + y).(x + y + 1) / 2 + x $
  • $ ⟨x_1, . ., x_n⟩_n $ je kód uspořádané n-tice daný: $ ⟨x_1, . . ., x_n⟩_n = ⟨x_1, ⟨x_2, . . ., x_n⟩_{n-1}⟩_2 $
  • $ π_{n,i}(⟨x_1, . ., x_n⟩_n) = x_i $ je inverze pro výběr $ i $-tého prvku ze zakódované $ n $-tice
  • Lemma – Pro každé $ n ≥ 2, i ≤ n $ jsou funkce $ ⟨x_1, . . . , x_n⟩_n $ a $ π_n $ PRF, a $ ⟨x_1, . . . , x_n⟩_n $ je bijekcí mezi $ N^{n+1} $ a $ N $ ( důkaz pro πn předpokládá, že omezená minimalizace a kvantifikace jsou PRF ).

Věta ( důsledek Kleeneho věty ) Predikát $ R ⊆ N^n $ je RSP ⇔ ∃ PRP $ P ⊆ N^{n+1} $ , že: $ R(x_1, . . , x_n) ⇔ (∃y)[P (x_1, . . , x_n, y)] $.

Věta ( RSP jsou uzavřeny na ∃ kvantifikátor ) $ P(x_1, \dots, x_n, y) $ je RSP ⇒ $ R(x_1, \dots, x_n)=(\exists y)\;[P(x_1, \dots, x_n, y)] $ je RSP

Dk
Protože $ P(x, y) $ je RSP, můžeme jej zapsat podle důsledku Kleeneho jako $ P(x, y) = (∃z) [Q(x, y, z)] $, kde $ Q $ je PRP. Z toho plyne, že $ R(x) = (∃y)(∃z) [Q(x, y, z)]= (∃⟨y, z⟩_2) [Q(x, y, z)] $.
Označíme-li si $ D(x, u) = Q(x, π_{2,1}(u), π_{2,2}(u)) $, pak $ D $ je PRP, pro který platí, že $ R(x) = (∃u) D(x, u) $.
⇒ podle důsledku Kleeneho: $ R(x) $ je RSP.

Věta ( výběrová funkce ) $ R(x, y) $ je RSP ⇒ $ \exists $ ČRF $ f $ (také výběrová funkce nebo selektor pro $ R $), že $ f(x)\downarrow\Leftrightarrow(\exists y)R(x, y) $ a pokud $ f(x)\downarrow $, pak $ R(x, f(x)) $.

💡 $ \exists f $ implementující $ \exists y $ na predikátu $ R(x, y) $

Dk
Podle důsledku Kleeneho můžeme $ R $ zapsat jako $ R(x, y) = (∃z)[Q(x, y, z)] $ pro nějaký PRP $ Q $. A tedy $ (∃y)R(x, y) ⇔ (∃y)(∃z)Q(x, y, z) $. Protože predikát $ Q $ je PRP(totální), dostaneme, že funkce $ g(x) ≃ μ⟨y, z⟩_2 Q(x, y, z) $.
Nyní z nalezené hodnoty stačí vybrat $ y $, tedy 1. prvek, celkově tedy definujeme funkci $ f $ jako $ f(x) ≃ π_{2,1}(g(x)) $.


další zdroje[editovat | editovat zdroj]

7. RM = rng rost. úsekové ČRF (🎓)[editovat | editovat zdroj]

Rekurzivní množina jako obor hodnot rostoucí úsekové funkce.

$ f $ je úseková fce, pokud její definiční obor tvoří počáteční úsek $ \mathbb N\,\! $

Věta ( $ RM = rng $ rostoucí úsekové ČRF ) A je RM $ \Leftrightarrow $ je oborem hodnot nějaké rostoucí úsekové ČRF

Dk (oběma směry - neformálně, zde formálnější přepis ze skript)

$ \Rightarrow\,\! $: Předpokládejme nejprve, že $ A $ je RM. Zkonstruujeme rostoucí, úsekovou ČRF $ f(i) $ = "vrať $ i $-tý nejmenší prvek z $ A $".

  • Začneme $ f(0) \simeq \mu x(x\in A)\,\! $.
  • Dále $ f(n+1) \simeq \mu x(x > f(n) \wedge x \in A)\,\! $

$ \Leftarrow\,\! $: Nyní předpokládejme, že $ A = rng f $, kde $ f\,\! $ je rostoucí úsekovou ČRF.

  1. Pokud $ f $ není ORF, znamená to že $ f\,\! $ má konečné $ dom\,\! $ (z def. úsekové fce), a tedy je konečná i samotná množina $ A $ a je tedy triviálně rekurzivní.
  2. Pokud je $ f $ ORF je všude definovaná (totální): $ y \in A=rng f \Leftrightarrow \exists x:f(x)=y \Leftrightarrow \exists x\!\leq\!y: f(x)=y $. Poslední ekvivalence platí, protože $ f\,\! $ je rostoucí a úseková. Tedy $ y \in A \Leftrightarrow y \in \{f(0),\ldots,f(y)\}. $

💡 Důsledek: Nechť $ A $ je ∞ množina: $ A $ je $ RM ⇔ A=rng $ nějaké rostoucí ORF. (protože úsekové funkce s nekonečnou doménou musí být všude definované = totální)

RSM = rng ORF, či ČRF (🎓)[editovat | editovat zdroj]

Rekurzivně spočetná množina jako obor hodnot obecně rekurzivní funkce, či částečně rekurzivní funkce.

Zážitky ze zkoušek  
  • Funckia f je CRF ⇔ jej graf je RSM
    • Na ustnej sa ma pytal (kedze som to tam nemal uplne jasne vysvetlene, hlavne ze preco je riesenie korektne v jednom ⇔ ak je v prevedenom) veci ohladne toho, ale dost ma navadzal a spolu s nim som to tam aj vymyslel.
    • mi prošla bez dotazů, jsou to dvě věty, tak nějak jsem nastínil i důkazy, jen na pár řádek, zřejmě mu stačilo vidět myšlenku


Věta ( Generování RSM ) Následující tvrzení jsou ekvivalentní:

  1. A je RSM.
  2. A je ∅, nebo je $ rng $ nějaké ORF
  3. A je $ rng $ nějaké ČRF.
  4. A je $ rng $ nějaké rostoucí ČRF.
Dk (neformální, zde komplet)
postup v dukazu

$ 1. ⇒ 2. $ (konstrukce ORF co pro jakékoli vstupy vrací prvky z A):

$ g(z) ≃ φ_{s-1-1 (e1,e)}(z) ≃ φ_{e1}(e, z = ⟨x, s⟩_2) ≃ \begin{cases}x \quad & x ∈ W_{e,s} \\ π_{2,1}(μ⟨x, s⟩_2[x ∈ W_{e,s}])\quad & \mbox{ jinak }\end{cases} $.

Každý prvek $ W_e $ je tedy funkcí $ g $ pro nějaký vstup $ y $ vrácen, jenom nedokážeme odhadnout, pro jak velké $ y $. Dohromady dostáváme, že $ A = W_e = rng~ g $.

$ 2. ⇒ 3. $ : Plyne z toho, že každá ORF je i ČRF. ∅ je oborem hodnot ČRF, která není definovaná pro žádný vstup.

$ 3. ⇒ 1. $ (pomocí částečné aproximace vyrobíme z ČRF RSP => RSM): Předpokládejme, že $ A $ je oborem hodnot ČRF $ g ≃ φ_e $.

Uvědomme si, že rozhodnutí, zda $ g(y)↓= x $ je RSP (plyne například z toho, že $ φ_{e,s}(y)↓ = x $ je PRP a tedy $ g(y)↓ = x ⇔ (∃s)[φe,s(y)↓= x] $ je RSP, dále je tedy i $ (∃y)[g(y)↓ = x] $ RSP, a tedy množina $ A = \{x | (∃y)[g(y)↓ = x]\} $ je RSM. Ze znalosti GČ $ e $ funkce $ g $ bychom opět s pomocí s-m-n věty mohli spočítat GČ funkce, jejíž doménou množina $ A $ je. Pro úplnost totiž můžeme past $ A = dom~ λx [ μ⟨y, s⟩_2[φ_{e,s}(y)↓= x] ] $.

$ 1. ⇒ 4. $ (zkonstruujeme triviální rostoucí ČRF $ h(x)=g(e,x) $ u které se $ dom $=$ rng $) : Předpokládejme, že $ A = W_e $, tedy $ A = dom φ_e $. Buď $ g(e, x) $ fce definovaná jako:

$ g(e, x) = \begin{cases}x \quad & x ∈ W_e \\ ↑ \quad & \mbox{ jinak }\end{cases} $.
Funkce $ g(e, x) $ je zřejmě ČRF, například proto, že ji lze zapsat jako $ g(e, x) = o(φ_e(x)) + x $ (tj. do nulové funkce vložíme $ φ_e(x) $ jako argument, hodnota tedy na hodnote $ φ_e(x) $ nezávisí, definovatelnost ano). Položme nyní $ h(x) = g(e, x) $, potom je $ A $ jak oborem hodnot, tak definičním oborem funkce $ h $, funkce $ h $ je rostoucí ČRF, jejíž GČ lze opět efektivně spočítat z $ e $.

$ 4. ⇒ 3. $ : Toto je zřejmé. Implikaci $ (3. ⇒ 1.) $ už máme hotovou.

Tato část je neúplná a potřebuje rozšířit. {{{1}}}

1=>3

Pro každou množinu $ W_x $ vytvoříme množinu dvojic $ R=\{\langle y,y\rangle:y \in W_x\}\,\! $. Množina $ R\,\! $ je rekurzivně spočetná, tedy má ČRF selektor $ \varphi\,\! $, :platí $ dom(\varphi)=rng(\varphi)=W_x\,\! $.
Myšlenka toho důkazu je, že body, kde $ \varphi_x\,\! $ konverguje, vyneseme na diagonálu a vytvoříme selektor. Jeho definiční obor bude zárověň jeho oborem hodnot.

1<=3

Máme ČRF $ g\,\! $ a její obor hodnot. Zkonstruujeme pseudoinverzní funkci $ h\,\! $ k ČRF $ g\,\! $, tj. funkci takovou, že $ dom(h)=rng(g)\,\! $ a to tak, že vyrobíme RS :predikát $ Q(x,y)\Leftrightarrow g(x)\simeq y\,\! $ a to má ČRF selektor, který hledáme -- $ h\,\! $.

1, ≤m a jejich vlastnosti, K a K0 1-úplné, RSM a ¬RM.[editovat | editovat zdroj]

1-převoditelnost, m-převoditelnost a jejich vlastnosti, 1-úplnost množin K a K0. Množiny K a K0 jsou rekurzivně spočetné, ale nejsou rekurzivní.

$ A\leq_m B $ (množina $ A $ je $ m $-převoditelná na $ B $) pokud ∃ ORF $ f $, tž: $ ∀ x: x ∈ A ⇔ f(x) ∈ B $

$ A\leq_1 B $ (množina $ A $ je $ 1 $-převoditelná na $ B $) je-li $ f $ navíc prostá

množina $ A $ je $ m $-úplná (resp. $ 1 $-úplná) pro třídu RSM pokud: je $ A $ RSM a ∀ jiná RSM je na ni $ m $-převoditelná (resp. $ 1 $-převoditelná).

💡 budeme říkat pouze $ A $ je $ m $-úplná nebo $ 1 $-úplná, dodatek „pro třídu RSM“ budeme vynechávat, protože jinými než RM a RSM se nebudeme zabývat.

9.1 vlastnosti ≤1, ≤m[editovat | editovat zdroj]

  • $ A\leq_m B $ a $ B $ RM $ \Rightarrow A $ RM
💡 $ A\leq_m B $ a $ A $ není RM $ \Rightarrow B $ není RM (protože: $ (A\Rightarrow B)=(\neg B\Rightarrow \neg A) $)
Dk: Je-li $ B $ RM a $ f $ je ORF převádějící $ A $ na $ B $, pak $ x ∈ A ⇔ f(x) ∈ B $ a tedy $ χ_A(x) = χ_B(f(x)) $. $ χ_A $ je jistě ORF a tedy $ A $ je RM.
  • $ A\leq_m B $ a $ B $ RSM $ \Rightarrow A $ RSM
💡 $ A\leq_m B $ a $ A $ není RSM $ \Rightarrow B $ není RSM
Dk: Je-li $ B $ RSM a platí-li $ B = dom φ_e $ a je-li $ f $ ORF, která převádí $ A $ na $ B $, pak $ A = dom λx[φe(f(x))] $ a jde tedy o RSM.
  • $ \leq_m $ a $ \leq_1 $ (relace) jsou reflexivní a tranzitivní
Dk: To, že jsou $ ≤_m $ a $ ≤_1 $ reflexivní relace plyne z toho, že identita je prostá ORF. Předpokládejme, že $ A ≤_1 B $ a $ B ≤_1 C $, nechť $ f $ je prostá ORF převádějící $ A $ na $ B $ a $ g $ buď prostá ORF převádějící $ B $ na $ C $. Pak $ h(x) = g(f(x)) $ je prostá ORF která převádí $ A $ na $ C $, což ukazuje, že $ ≤_1 $ je tranzitivní. Pro $ ≤_m $ platí týž argument s vynecháním prostoty.
  • $ A $ $ m $-úplná & $ B $ RSM & $ A\leq_m B \Rightarrow B $ je $ m $-úplná
💡 platí pro 1-převoditelnost a 1-úplnost
Dk: Toto plyne okamžitě z tranzitivity $ ≤_m $, $ ≤_1 $ a definice úplnosti.
  • $ A\leq_mB \Rightarrow \overline A\leq_m\overline B $
💡 platí pro 1-převoditelnost a 1-úplnost
Dk: Plyne přímo z definice převoditelnosti, převod $ A $ na $ B $ zajistí stejná funkce jako převod $ A $ na $ B $.

Problém zastavení K0 a jeho diagonála K[editovat | editovat zdroj]

$ K_0 =\{\langle x, y\rangle_2\;|\;\varphi_x(y)\downarrow\}=\{\langle x, y\rangle_2\;|\;y\in W_x\} $ - problém zastavení
$ K =\{x\;|\;\varphi_x(x)\downarrow\}=\{x\;|\;x\in W_x\} $ - diagonála $ K_0 $

💡 $ K_1 =\{x\;|\;W_x\neq\emptyset\} $

Věta ( $ K $, $ K_0 $ RSM $ \neg $RM ) $ K $ a $ K_0 $ jsou RSM, ale nejsou RM

Dk (sporem jako u TS)
Z definice jsou obě RSM. Nechť $ φ_z $ označuje univerzální ČRF.
$ K = dom λx[φ_z(x, x)] $. Pro spor $ K $ je RM ⇒ $ \overline K $ je RSM.
Nechť $ φ_e $ je ČRF, pro níž $ \overline K = dom φ_e $ a ptejme se, zda $ e ∈ \overline K $ nebo ne:
Z def. $ K $$ e ∈ \overline K ⇔ φ_e(e)↑ $
$ \overline K = dom φ_e $$ e ∈ \overline K ⇔ φ_e(e)↓ $
$ φ_e(e)↓ ⇔ φ_e(e)↑ $SPOR$ K $ tedy není RM.
$ K_0 = dom λ⟨x, y⟩_2[φ_z(x, y)] $. Pro spor $ K_0 $ je RM a $ χ_{K0} $ je její char. ORF:
Definujeme $ χ_{K}(x) = χ_{K_0}(⟨x, x⟩_2) $$ χ_K $ char. ORF $ K $SPOR s tím že $ K $ není RM. ⇒ $ K_0 $ tedy není RM.

Věta ( 1-úplnost $ K $, $ K_0 $ ) Množiny $ K $ a $ K_0 $ jsou 1-úplné.

Dk
$ K $ je $ 1 $-úplná: $ K $ je RSM, stačí tedy ukázat, že libovolnou RSM lze na $ K $ převést prostou ORF.
Definujme funkci $ φ_{e1}(e, x, y) ≃ φ_e(x) $. Podle s-m-n věty $ φ_{s^2_1(e1,e,x)} (y) ≃ φ_e (e, x, y) ≃ φ_e(x) $. Definujme tedy funkci $ f(e, x) = s_1^2(e_1, e, x) $. Protože $ s_1^2 $ je prostá PRF, je i $ f $ prostá PRF. Navíc platí, že $ φ_{f(e,x)} $ je buď všude definovaná konstantní funkce, pokud $ x ∈ W_e $, nebo jde o funkci, která není definovaná pro žádný vstup v případě, že $ x \notin W_e $, platí tedy, že:
$ x ∈ W_e ⇒ φ_e(x)↓ ⇒ (∀y)[φ_{e1} (e, x, y)↓] ⇒ φ_{f(e,x)}(f(e, x))↓ ⇒ f(e, x) ∈ K $
$ x\notin W_e ⇒ φ_e(x)↑ ⇒ (∀y)[φ_{e1} (e, x, y)↑] ⇒ φ_{f(e,x)}(f(e, x))↑ ⇒ f(e, x) \notin K $
Dohromady dostaneme požadovanou ekvivalenci $ x ∈ W_e ⇔ f(e, x) ∈ K $, a z toho plyne, že funkce $ g(x) $ definovaná jako $ g(x) ≃ f(e, x) $, je prostá ORF, která převádí množinu $ W_e $ na $ K $. Protože $ W_e $ byla libovolná množina, dostáváme, že $ (∀e)[W_e ≤_1 K] $, a $ K $ je tedy $ 1 $-úplná množina.
$ K_0 $ je RSM (podle vlastností převoditelnosti). Ve větě nahoru jsme ukázali i to, že $ K ≤_1 K_0 $ pomocí prosté ORF $ h(x) = ⟨x, x⟩_2 $. Těžkost množiny $ K_0 $ tedy plyne z tranzitivity $ 1 $-převoditelnosti.

Riceova v. - dk převoditelnost[editovat | editovat zdroj]

Riceova věta - důkaz pomocí převoditelnosti.

Věta ( Rice ) $ \cal C $ třída ČRF, $ A_\cal C = \{e | \varphi_e ∈ C\} $ je RM ⇔ $ \cal C = \emptyset $ nebo $ \cal C $ obsahuje všechny ČRF

💡  $ A_\cal C $ je mnozina indexu (Gödel.č.) funkci z třídy $ \cal C $

Dk (pomocí převoditelnosti)
předpokládejme že $ \cal C $ NEní ∅ a $ \cal C $ NEobsahuje všechny ČRF
ukážeme sporem že $ K ≤_1 A_\cal C $
$ e_0 $ je GČ fce nedefinové pro žádný vstup a $ φ_{e0} ∈ \overline{\cal C} $
$ e_1 $ je GČ fce $ φ_{e1}∈C $ a $ φ_{e0}≄ φ_{e1} $
$ \varphi_{e_2}(x, y)\simeq\cases{ \varphi_{e_1}(y)&je-li $x\in K$\cr \uparrow } $
$ φ_{e2}(x , y) ≃ φ_{s^1_1}(e, x) (y) ≃ φ_{f(x)}(y) $
$ x∈K ⇒ φ_{f(x)}≃φ_{e1} ⇒ φ_{f(x)}(y) ∈ C ⇒ f(x) ∈ A_\cal C $
$ x∉K ⇒ φ_{f(x)}≃φ_{e0} ⇒ φ_{f(x)}(y) ∉ C ⇒ f(x)∉ A_\cal C $
tedy $ x ∈ K ⇔ f(x) ∈ Ac $

VoR a důsledky (🎓)[editovat | editovat zdroj]

Věta o rekurzi a její jednoduché důsledky (ne Riceova věta)

Zážitky ze zkoušek  
  • Věty o rekurzi, došlo i na tu obligátní otázku, jestli počítá rychleji f(a) nebo a, od ní jsme se dostali až k Riceově větě a okrajově i k důkazu nerozhodnutelnosti halting problému
  • Věta o rekurzi a její aplikace. Zkoušejícího zajímalo znění, důkaz (preferoval ten přes s-m-n větu, ale spokojil se i s diagonalizačním), aplikace (Riceova věta a její znění, existence množin jako $ Wx=\{x\} $ s důkazem).
  • Věty o rekurzi, Riceova věta - Napsal jsem základní větu, generování pevných bod a větu o rekurzi v závislosti na parametrech (vše samozřejmě s těmi jednoduchými důkazy). Napsal jsem Riceovu větu a její důkaz plynoucí ze základní věty o rekurzi. Ptal se mě odkud plynou důkazy, odpovědel jsem, že z Kleeneho věty a s.m.n. Pak se ještě ptal na trochu jinou verzi "Věty o programu co vypíše sám sebe", tam jsem trochu tápal, ale intuitivně jsem věděl (tu větu jsem znal, bohužel jsem ji neuvedl).


Věta ( VoR ) ∀ ORF $ f $$ n $: $ φ_n ≃ φ_{f(n)} $

💡 ∀ ORF transformacni funkci algoritmu f ∃ n tak že oba TS počítají stejnou fci (mají stejný algoritmus)
💡 n se říká pevný bod f
Dk (přes s-m-n větu)
Nechť $ e_1 $ je číslem funkce, pro kterou platí $ \varphi_{e_1}^{(2)}(e, x)\simeq\varphi_{f(\varphi_e(e))}(x), $ tuto funkci bychom snadno odvodili pomocí univerzální ČRF.
Nechť $ b $ je Gödelovým číslem funkce $ s_1^1(e_1, e) $, podle s-m-n věty tedy platí, že $ \varphi_{\varphi_b(e)}(x)\simeq\varphi_{s_1^1(e_1, e)}(x)\simeq\varphi_{e_1}^{(2)}(e, x)\simeq\varphi_{f(\varphi_e(e))}(x). $
Protože $ \varphi_b $ je PRF (podle s-m-n), je $ \varphi_b(b)\downarrow $ a platí, že $ \varphi_{\varphi_b(b)}\simeq\varphi_{f(\varphi_b(b))}, $ $ \varphi_b(b) $ je tedy hledaným pevným bodem $ f $.
Tato část je neúplná a potřebuje rozšířit. doplnit poznámky

Důsledky VoR[editovat | editovat zdroj]

Věta ( 💡 ) ∃ prostá PRF $ g $, která ke GČ funkce $ f $ určí její pevný bod

Věta ( 💡 ) ∀ ORF $ f $ má ∞ pevných bodů

Věta ( 💡 )$ n ∈ N $, pro nějž:

  1. $ W_n = \{n\} $
  2. $ φ_n ≃ λx[n] $
Dk
  1. Nechť $ e $ je Gödelovo číslo funkce definované jako $ φ_e^{(2)}(x, y) ≃ μz[x = y] $ (💡 tedy $ φ_e^{(2)}(x, y)↓ $$ x = y $). Použijeme s-m-n větu a definujeme-li $ f(x) ≃ s_1^1(e, x) $, dostaneme, že $ φ_{f(x)} ≃ φ_{s-1-1(e,x)} ≃ φ_e(x, y) $ a tedy $ W_{f(x)} = \{x\} $. Funkce $ f $ je ORF (podle s-m-n), a tak podle VoR: $ ∃ n: φ_n ≃ φ_{f(n)} $, a tak $ W_n = W_{f(n)} = \{n\} $.
  2. Podobně, nechť $ e $ je GČ funkce definované jako $ φ_e^{(2)}(x, y) ≃ x $. Pomocí s-m-n věty definujeme-li $ f(x) = s_1^1(e, x) $, dostaneme $ φ_{f(x)}(y) ≃ x $ a s použitím VoR nalezneme $ n $, pro něž je $ φ_n(y) ≃ φ_{f(n)}(y) ≃ n $.

Věta ( VoR s parametry ) $ f(x,y) $ je ORF $ ⇒ ∃ $ prostá ORF $ n(y) $ taková, že $ φ_{n(y)} ≃ φ_{f(n(y),y)} ∀y ∈ N $

Riceova v. - dk s VoR (🎓)[editovat | editovat zdroj]

Věta ( Rice ) $ \cal C $ třída ČRF, $ A_\cal C = \{e | \varphi_e ∈ C\} $ je RM ⇔ $ \cal C = \emptyset $ nebo $ \cal C $ obsahuje všechny ČRF

Dk (sporem)
předpokládejme že $ \cal C $ NEní ∅ a $ \cal C $ NEobsahuje všechny ČRF
předpokládejme sporem že $ A_\cal C $ je rekurzivní
definujme si fci $ f $:
$ f(x) = a ~~ x∉ A_\cal C $
$ f(x) = b ~~ x∈ A_\cal C $
$ f $ je ORF
$ a∈A_\cal C $
$ b∉ A_\cal C $
$ n $ je pevný bod $ f $ a $ φ_n≃ φ_{f(n)} $
$ φ_n∈\cal C ⇒ n ∈ A_\cal C ⇒ f(n)=b ⇒ f(n)∉ A_\cal C ⇒ φ_{f(n)} ∉ \cal C $
$ φ_n∉\cal C ⇒ n ∈ A_\cal C ⇒ f(n)=a ⇒ f(n)∈ A_\cal C ⇒ φ_{f(n)}∈ \cal C $
spor

Složitost[editovat | editovat zdroj]

(Complexity)

Def. základních tříd složitosti. Definice třídy NP pomocí cert. a NTS a jejich ekvivalence. ≤pm, NPC a jejich vlastnosti (🎓)[editovat | editovat zdroj]

Definice základních tříd složitosti. Definice třídy NP pomocí certifikátů a nedeterministických strojů a jejich ekvivalence. Polynomiální převoditelnost a úplnost a jejich vlastnosti

Definice základních tříd složitosti[editovat | editovat zdroj]

typy problémů:

  • odpověď typu ano/ne - rozhodovací problém (jestli vstup patří do binární relace $ L\subseteq\{0, 1\}^* $)
    • vstup - instance problému
  • úloha - pro daný vstup x nalézt y co splňuje požadovanou vlastnost (jestli oba patří do binární relace $ R\subseteq\{0, 1\}^*\times\{0, 1\}^* $)
třídy jazyků a relací (tj. problémů a úloh)

💡 $ f:\mathbf N\mapsto\mathbf N $ libovolná fce

  • $ DTIME(f(n)) $, jazyk $ L(M) ∈ DTIME(f(n)) ⇐ $ ∃ TS $ M $ co pracuje v čase $ O(f(n)) $.
  • $ DSPACE(f(n)) $, jazyk $ L(M) ∈ DSPACE(f(n)) ⇐ $ ∃ TS $ M $ co pracuje v prostoru $ O(f(n)) $.
  • $ DTIMEF(f(n)) $, relace $ R ∈ DTIMEF(f(n)) ⇐ $ ∃ TS $ M $ co pracuje v čase $ O(f(n)) $, $ M(x) $ přijme ⇔ ∃ slovo $ y $: $ (x, y)\in R $ a na konci páska obsahuje $ y $
💡 Lze to také říci tak, že selektor pro predikát R je funkce spočitatelná v polynomiálním čase.

Lemma $ DTIME(f(n)) ⊆ DSPACE(f(n)) $

Definice třídy NP[editovat | editovat zdroj]

Třídy polynomiálních jazyků, relací:

  • $ P= \bigcup_{i\in \mathbb N}DTIME(n^i) $ - problémy rozhodnutelné v polynomiálním čase
  • $ PSPACE=\bigcup_{i\in\mathbb N}DSPACE(n^i) $ - problémy rozhodnutelné v polynomiálním prostoru
  • $ PF=\bigcup_{i\in\mathbb N}DTIMEF(n^i) $ - úlohy řešitelné v polynomiálním čase

Třída polynomiálně ověřitelných úloh $ NPF $ ($ NP $ - nedeterministicky polynomiální, $ F $ - funkce, úlohy řešitelné nedeterministickým Turingovým strojem v polynomiálním čase)

  • Relace $ R ∈ NPF $ ⇐ ∃ polynom $ p(n) $: že $ ∀ (x, y)\in R $ je $ |y|\leq p(|x|) $ a ověření zda $ (x, y)\in R $ lze v polynomiálním čase.

Třída polynomiálně ověřitelných problémů $ NP $ (nedeterministicky polynomiální)

  • def. pomocí certifikátů: Jazyk $ L ∈ \mathrm NP $ ⇐ ∃ polynom $ p $ a jazyk $ B\in P $ a pokud $ ∀ x\in\{0, 1\}^* $ platí: $ x\in L\Leftrightarrow (\exists y)\;\Big[|y|\leq p(|x|)\mbox{ a }(x, y)\in B\Big]. $
💡 $ L ∈ \mathrm NP $ ⇐ ∃ polynomiální algoritmus (daný jazykem $ B $), že polynomiálně dlouhý certifikát $ y $ dosvědčuje fakt $ x\in L $. Je opět nutné uvažovat pouze polynomiálně dlouhé certifikáty, neboť složitost ověřování se měří vzhledem k délce $ x $ i certifikátu $ y $.
💡 obecně platí P ⊆ NP, protože pokud umíme problém řešit polyn. nepotřebujeme certifikát
  • def. pomocí NTS:
💡 NTS $ M=(Q, \Sigma, \delta, q_0, F) $, kde $ \delta:Q\times\Sigma\mapsto\cal P(Q\times\Sigma\times\{R, N, L\}) $.
třídy jazyků a relací (tj. problémů a úloh)
💡 $ f:\mathbf N\mapsto\mathbf N $ libovolná fce
$ NTIME(f(n)) $, jazyk $ L(M) ∈ NTIME(f(n)) ⇐ $ ∃ NTS $ M $ co pracuje v čase $ O(f(n)) $.
$ NSPACE(f(n)) $, jazyk $ L(M) ∈ NSPACE(f(n)) ⇐ $ ∃ NTS $ M $ co pracuje v prostoru $ O(f(n)) $.

Věta ( ekvivalence definic NP ) $ NP=\bigcup_{i\in\mathbb N} NTIME(n^i) $

Dk (přes oba směry implikace)
→ : Předpokládejme nejprve, že L ∈ NP, to znamená, že ∃ polynom p a jazyk B ∈ P, pro které platí, že x ∈ L právě když existuje y, |y| ≤ p(|x|), pro které (x, y) ∈ B. NTS M’ , který bude přijímat L, bude pracovat ve dvou fázích. V první fázi zapíše na vstupní pásku za slovo x slovo y, tato fáze je nedeterministická a pro každé slovo y, takové že|y| ≤ p(|x|) existuje výpočet M’, který jej napíše. Na zápis y stačí čas p(|x|). Ve druhé fázi bude M’ simulovat práci TS M, který rozpoznává jazyk B, na vstupu (x, y), přičemž přijme, pokud (x, y) ∈ B. Zřejmě L = L(M) a M pracuje v polynomiálním čase.
← : Nyní předpokládejme, že L ∈ ∪i∈N NTIME(ni). To znamená, že x ∈ L právě když existuje polynomiálně dlouhý výpočet nedeterministického Turingova stroje M, kde L = L(M), jenž x přijme. V každém kroku tohoto výpočtu vybírá M z několika možných instrukcí, nechť řetězec y kóduje právě to, které instrukce byly v každém kroku vybrány. Řetězec y má délku nejvýš p(|x|) pro nějaký polynom p, protože M pracuje v polynomiálním čase a možností jak pokračovat z dané konfigurace podle přechodové funkce je jen konstantně mnoho. Simulací M s použitím instrukcí daných dle y můžeme deterministicky ověřit, zda y kóduje přijímající výpočet. Řetězec y tedy může sloužit jako polynomiálně dlouhý certifikát kladné odpovědi.

Polynomiální převoditelnost, úplnost a jejich vlastnosti.[editovat | editovat zdroj]

Ilustrace polynomiálního převodu/redukce z jazyka $ L_1 $ na jazyk $ L_2 $ pomocí redukční fce $ f $. Pro vstup $ x∈\{0,1\}^* $ má otázka zda $ x∈L_1 $ stejnou odpověď jako otázka zda $ x∈L_2 $. 💡 myslím že je vidět proč se mu říká někdy redukce($ f $ NENÍ prostá)
Ilustrace polynomiálního převodu/redukce z jazyka $ L_1 $ na jazyk $ L_2 $ pomocí redukční fce $ f $. Pro vstup $ x∈\{0,1\}^* $ má otázka zda $ x∈L_1 $ stejnou odpověď jako otázka zda $ x∈L_2 $. 💡 myslím že je vidět proč se mu říká někdy redukce($ f $ NENÍ prostá)
$ {NP} $-těžkost
$ {NP} $-těžkost

$ A\leq_m^pB $ (jazyk $ A $ polynomiálně převoditelný/redukovatelný na $ B $) pokud f: {0,1}*→{0, 1}* spočitatelná v polynomiálním čase a platí: $ x ∈A ⇔f(x) ∈B $

vlastnosti:

  • $ \leq_m^p $ je reflexivní a tranzitivní.
Dk: Reflexivita plyne z toho, že identita je funkce spočitatelná v polynomiálním čase. Tranzitivita plyne z toho, že složením dvou polynomů vznikne opět polynom, přesněji, je-li f funkce převádějící jazyk A na jazyk B, tedy A ≤mp B s použitím f, a g je funkce převádějící jazyk B na jazyk C, tedy B ≤mp C s použitím g, pak g ◦ f převádí A na C, jsou-li f i g spočitatelné v polynomiálním čase, lze totéž říci i o g ◦ f, tedy A ≤mp C s použitím g ◦ f.
  • $ A\leq_m^pB $ a $ B\in P $$ A\in P $
Dk: Je-li B ∈ P, pak existuje Turingův stroj M, který přijímá B v polynomiálním čase. Je-li f funkce, která převádí A na B, a je-li f spočitatelná v polynomiálním čase, pak TS M’, který pro vstup x spočítá f(x) a poté pustí M k rozhodnutí, zda f(x) ∈ B, přijímá A v polynomiálním čase.
  • $ A\leq_m^pB $ a $ B\in NP $$ A\in NP $
Dk: Platí z téhož důvodu jako { 2. }, protože tytéž argumenty lze použít i pro NTS.
Eulerův diagram pro P, NP, NPC a NP-těžké množiny problémů. Levá strana platí pro $ P≠NP $, a pravá pro $ P=NP $ (až na prázdný jazyk a jeho doplněk nejsou nikdy NPC)

Jazyk $ A \in \mathbf{NP} $-hard (NP-těžký) ⇐ ∀ jazyk $ B\in NP $: $ B\leq_m^pA $.

Jazyk $ A \in \mathbf{NPC} $ (NP-Complete, NP-úplný) ⇐ $ A \in NP $ a $ A \in NP $-hard.

💡 problem je T-uplny, pokud patri do T a je T-silny, tedy kazdy problem v T se da na problem prevest v poly case

Věta ( ) A, B ∈ NP, $ A\leq_m^pB $ je NP-úplný ⇒ B je NP-úplný

Dk
Tvrzení plyne přímo z tranzitivity relace $ ≤_m^p $ zaručené vlastnostami polynomiální převoditelnosti a definice NP-úplného problému.

Definice (existence certifikátu – CERT, rozhodovací problém):

  • Instance : Řetězec w kódující DTS M, řetězec x a řetězec 1ᵗ pro nějaké t ∈ N.
  • Otázka : Existuje řetězec y s |y| ≤ t, pro který platí, že M(x, y) přijme v t krocích?

Věta ( NP-úplnost CERT ) Problém CERT je NP-úplný.


Savičova věta.[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • Státnice: Napsal jsem vetu, myslenku dukazu (sestrojime turingac, simulujeme vsechny vetve, recyklujeme + pamatujeme stavy...) v pohode stacilo, zeptal se me jeste na par otazek a o.k.
  • Státnice(I1): Trochu predbehnu - v prubehu zkouseni jsem se zeptal, zda je na pruchod touto otazkou nutno umet vetu dokazat. Odpoved:ano, idea dukazu nestaci. V mych materialech, jsem mel zneni nepresne [s rovnitkem namisto podmnozinitka mezi NSPACE a DSPACE. Rovnost je az ve vztahu NPSPACE a PSPACE]. Trval jsem na rovnitku s tim, ze jedna implikace je trivialni, [PK] si nebyl jisty, ze to takto plati a rekl at teda prejdu rovnou k te druhe implikaci(soudim, ze pro me to byly body dolu). Dukaz jsem delal na eng.Wikipedii. Nejprve jsem [spatne] zapsal algoritmus tak, ze snizoval delku cesty jen o 1 vrchol v kazdem zanoreni. [PK] nerekl co je spatne, ale chtel hned zanalyzovat prostorovou slozitost. Podrobne az na uroven zda se nacitani vstupu pocita nebo ne. Zde vyplynulo, "ze je neco spatne je" (napr. uz jen proto, ze pokud jen odecitam jednicku, nemusim pouzivat tento algoritmus, ale mohu proste prohledavat stavy do hloubky). V predpokladech jsem mel blbe "f nalezi o(log(n))" namisto "f nalezi male ci velke omega(log(n))". Nevzpominam si presne, ale rozdil (pro "o" vs. "omegy") byl v tom, ze jeden dovoluje prostor potrebny pro vstup stroje predpokladat "zadarmo" u druheho jej musim zapocitat do prost.slozitosti. Nahradil jsem odecitani jednicky pulenim intervalu a spolecne jsme uvarili prostorovou slozitost. Doplnujici otazky: def. prostorove konstruovatelna fce, ktere fce jsou prostorove konstruovatelne - ve smyslu je jich dostatecne (k rozumnemu analyzovani algoritmu)? Mj. jsem povedel, ze "problem maji ty vydatne sublinearni" s cimz [PK] nesouhlasil (log(n) je prostorove konstruovatelna - ale loglog(n) uz ne). Obecne [PK] jde do velkych detailu, zustava mily, dava prostor. Tato otazka byla nejspis za 3. U tohoto zkousejiciho velmi doporucuju pripravit si otazku na papir a precizne, nez povidat spatra o coz jsem se pokousel.



Věta ( počet konfigurací TS/NTS ) Nechť $ M $ je libovolný TS (DTS nebo NTS), který pracuje v prostoru $ f(n) $, pak existuje konstanta $ c_M $ (jejíž hodnota je závislá na stroji $ M $), pro kterou platí, že počet konfigurací $ M $ je nejvýš $ 2^{c_M f(n)} $.

Dk
Nechť $ M = (Q, Σ, δ, q_0, F ) $. Konfigurace se skládá ze slova na pásce, polohy hlavy v rámci tohoto slova a stavu, v němž se stroj $ M $ nachází. Délka slova na pásce je omezená $ f(n) $, počet různých poloh hlavy v rámci tohoto slova je $ f(n) $ a počet stavů je $ |Q| $. Počet konfigurací je tedy shora omezen pomocí $ |\Sigma|^{f(n)}f(n)|Q|\stackrel{rozepíšeme~pomocí~log}{=}2^{f(n)\log_2|\Sigma|}2^{\log_2f(n)}2^{\log_2|Q|}= 2^{f(n)\log_2|\Sigma|+\log_2f(n)+\log_2|Q|}\leq 2^{f(n)\cdot(\log_2|\Sigma|+1+\log_2|Q|)} $. Stačí tedy zvolit $ c_M = (log_2|Σ| + log_2|Q| + 1) $.
(💡 ani nemusíme používat 2ku stačí nějaká konstanta $ c $)

Věta ( Savičova, pro polynomy ) $ NPSPACE = PSPACE $

💡 hloubka rekurze $ Dosažitelná(i, K_0, K_F) $
Dk (NPSPACE ⊇ PSPACE)
∀ DTS je zvláštním případem NTS
Dk (NPSPACE ⊆ PSPACE - neformální dk, zde zkrácený přepis dk ze skript nebo originální dk ve skriptech)
Pro NTS (pracující v NPSPACE) zkonstruujeme DTS pracující v polynomiálním prostoru (💡 i když čas může být exponenciální).
Nechť NTS $ M $ přijímající $ L(M) $ v prostoru $ O(p(n)) $, pak DTS $ M’ $ přijímající stejný $ L $ pracující v polynomiálním prostoru může být zkonstruován pomocí bool rekurzivní funkce $ Dosažitelná(i, K_1, K_2) $, kde K jsou konfigurace NTS $ M $ a i je číslo.


$ Dosažitelná(i, K_1, K_2) $ vrátí:
  • true, pokud je $ K_2 $ dosažitelná z $ K_1 $ v nejvýše i krocích,
  • jinak false.
Tedy volání např $ Dosažitelná(i, K_1, K_2) $ rekurzivně zavolá $ ∀ K $: $ Dosažitelná(⌊i/2⌋, K_1, K) $ a $ Dosažitelná(⌈i/2⌉, K, K_3) $
(💡 alg. je zřejmě korektní)


Nechť $ w $ je vstupní slovo, zavoláme $ Dosažitelná(i, K_0, K_F) $ (💡 z počáteční konfigurace do BÚNO jediné přijímající) a $ i = 2^{c_M p(n)} $.
Potřebujeme $ hloubka=|log( 2 ^ {c_M p(n)} )| = O(p(n)) $ rekurzivních volání a $ prostor(K_i) = O(p(n)) $ místa na každé úrovni rekurze (💡 recyklace, 2 rekurzivní volání mohou používat stejný prostor).
Tedy $ prostor = hloubka\cdot prostor(K_i) = O(p(n))\cdot O(p(n)) = O(p(n)^2) $ místa na pásce pro všechna rekurzivní volání $ Dosažitelná $.
Druhá mocnina polynomu je stále polynom a takže: $ NPSPACE = PSPACE $.


další zdroje  


$ NPSPACE = PSPACE $

Věta ( Savičova, obecné znění ) Nechť $ f : N → N $ je funkce vyčíslitelná v prostoru $ O(f(n)) $, pro kterou platí, že $ f(n) ≥ log_2 n $ pro všechna $ n ∈ N $. Potom platí, že $ NSPACE(f(n)) ⊆ DSPACE(f^2(n)) $.

Dk
Důkaz předchozí věty nikde nevyužíval žádných zvláštních vlastností polynomů, můžeme jej tedy zobecnit a dostat tak obecnou Savičovu větu.
Ukázali jsme vlastně, že k otestování toho, jestli v obecném orientovaném grafu $ G=(V, E) $ vede cesta z daného vrcholu $ 0 $ do vrcholu $ F $, stačí prostor $ O((\log_2|V|)^2) $, pokud do tohoto prostoru nepočítáme prostor nutný k uložení grafu.
Pokud tedy místo polynomu $ p(n) $ použijeme obecnou funkci $ f(n) $, dostaneme tvrzení, že $ NSPACE(f(n))\subseteq DSPACE(f(n)^2) $.


Cook-Levin - KACHL ∈ NPC (🎓)[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • NP-uplnost (meno neviem, inicialy ML) Zacal som definiciou Turingovho stoja a postupne som definoval vsetko az po NP-uplnost, dokazal kachlikovani, prave ked som pisal prevod KACHL->SAT tak prisiel skusajuci, pozrel sa na to vsetko a povedal ze to staci.
  • Král: NP, NP-úplnost, příklady... Trochu jsem se zamotal do toho, jestli je třeba, aby se NTS zastavil po polynomiálním počtu kroků (v první chvíli jsem myslel, že ne a že když to bude třeba, tak že $ NTS = DTS $, ale to je blbost - třeba to sice není, ale pokud tak tu definici dáme, tak se nic nezmění). Byl hodný.
  • Matoušek - NP-úplnost - Přesná formální definice - rozhodovací problém, jazyk problému, NTS pro rozhodovací problém, složitost výpočtu NTS, NP. Převoditelnost aritmetických funkcí, problémů, NP-těžkost, NP-úplnost. Příklady problémů. Vztahy P, NP, NPC (obrázek s podmnožinami, je NPC doplněk k P v NP?). Alternativní definice NP přes ověřování řešení. Jak popsat NP, NPC laikovi.
  • NP-úplné problémy - Definoval jsem nedeterministický Turingův stroj, třídu NTIME, NP-úplnost a dokázal převod obecného NTS počítajícího nějaký NP problém na KACHL (Cook-Levinova věta). Na závěr jsem zmínil, že ještě existují další NP-úplné problémy např. SAT, Batoh, Obchodní cestující atd. Žádné další převody jsem nespecifikoval. Tato odpověď byla přijata bez jediné otázky.
  • Definoval jsem jazyk, problem, NP, prevody, NP-uplnost a strucne predvedl dukaz cook levina. Zkousejiciho opet neznam, ptal se jen na to jake dalsi NP-uplne problemy, jinak byl spokojen
  • Čepek (příseděl Koubek a Dvořák) - Úplné problémy pro třídu NP, Cook-Levinova věta. - Člověk by řekl, že jednoduchá otázka, ale kurevsky mi zatopila, neb jsem nebyl schopen dát do kupy přesnou definici NP a převoditelnosti pomocí TS (a Čepek 5 minut před tím jednoho kolegu vyhodil, neb neznal definici). Naštěstí mě několikrát nakopli a tak jsme nakonec došli k tomu, co to teda je NP-úplný problém. C-L větu + důkaz převodem na kachlíkování jsem uměl, což Čepka evidetně potěšilo, takže nakonec v pohodě.
  • definice NP, prevoditelnost, NPC, prevod na kachlikovani a na SAT
  • Koubek: definoval jsem NP, NPC, atd., dokazal vetu kachlikovanim. Pak se me ptal co znamena pojem uplnosti obecne a naky jeho zneni nebo dusledek Cook-Levinovy vety (neco jako ze kdyz bych umel polynomialne resit NPC problem, tak uz vsechny NP problemy jdou resit polynomialne). Pak chtel co je PSPACE uplnost a nakej priklad (obecna booleovska formule). SAT ve zneni s KNF se mu uplne nelibil, prej se vetsinou definuje obecne. Kdyz mu prisedici Majerech rikal, ze jak jsem ho definoval se to u nas vetsinou dela, tak se Koubek mracil :)
  • Hladík - Úplné problémy pro třídu NP + Cook Levinova věta. - Definice (od TS až k NPÚ), Důkaz Cook Levinovy věty (KACHL + převod na SAT), vyjmenovat problémy co byly na přednášce (zadání, otázka), ukázat převod SAT na KLIKA.
  • NP-úplné problémy (Klazar) - Dal jsem do kupy důkaz úplnosti kachlíkování, pár převodů, ani mi je nenechal všechny přeříkat. Nakonec se zeptal, kam patří PRIMES (rozhodnout, zda něco je prvočíslo) - bez důkazu


Kachlíkování (KACHL, anglicky Tiling)

  • Instance: Množina barev B, přirozené číslo s, čtvercová síť S velikosti s x s, hrany jejíchž krajních políček jsou obarveny barvami z B. Dále je součástí instance množina K⊆BxBxBxB s typy kachlíků, které odpovídají čtverci, jehož hrany jsou obarveny barvami z B. Tyto kachlíky mají přesně definovaný horní, dolní, levý i pravý okraj a není možné je otáčet.
  • Otázka: Existuje přípustné vykachlíkování čtvercové sítě S kachlíky z množiny K? Přípustné vykachlíkování je takové přiřazení typů kachklíků jednotlivým polím čtvercové sítě S, v němž kachlíky, které spolu sousedí mají touž barvu na vzájemně dotýkajících se hranách a kachlíky, které se dotýkají strany S, mají shodnou barvu s okrajem. Jednotlivé typy kachlíků lze použít víckrát.

Věta ( Cook-Levin ) KACHL je NP-úplný problém.

💡  neboli splnitelnost SAT je NP-úplná (tedy je nutne prevest KACHL na SAT ale to neni nutne dokazovat)

Dk
DTS->kachl; barva pro vsechny symboly * vsechny stavy; specialni barva pro posun hlavy vlevo/vpravo
spodni okraj vstupni paska, obarveni vystupniho okraje je vystupni paska
alt.: existuje vykachlikovani?


Dk(Myšlenka důkazu)
  • Kachl je v NP (jistě jde verifikovat v polynomiálním čase)
  • Kachl je NP těžký
    • Vezměme libovolný problém z NP, pak jeho nedeterministický turingáč řeší, jestli $ I \in L $ (zda řetězec $ I $ patří do jazyka $ L $, neboli zda jeho nedeterministický turingáč přijme daný vstup $ I $) v polynomiálním čase polynomu $ P $
    • Zkonstruujeme síť $ P\times P $, zkonstruujeme vhodné kachličky (7 druhů) a obarvení (barvy jsou z množiny $ ABECEDA \cup (STAVY \times ABECEDA) \cup \lbrace q_l, q_r | q \in STAVY \rbrace $ tak, aby
      • Každý krok výpočtu NTS kódoval jeden vykachličkovaný řádek. NTS pracuje "paralelne" (existuje vice zpusobu vypoctu), takze si muzeme predstavit strom vypoctu, kde vetveni zajistuje prechodova funkce. Simulovat NTS pomoci deterministickeho TS zvladneme prochazenim tohoto stromu do sirky (nikoli do hloubky!)
      • Každý řádek popisoval jeden krok výpočtu NTS
  • Tím jsme nalezli NP-úplný problém
Tato část je neúplná a potřebuje rozšířit.
Dk(NTS → KACHL)

Všimněme si nejprve, že $ KACHL ∈ NP $. To plyne z toho, že dostaneme-li vykachlíkování sítě $ S $, tedy přiřazení typů kachlíků jednotlivým políčkům, dokážeme ověřit v polynomiálním čase, jde-li o přípustné vykachlíkování. Ve skutečnosti úloha nalezení správného vykachlíkování je polynomiálně ověřitelná a patří tedy do NPF, proto její rozhodovací verze patří do NP. Nechť $ A ⊆ \{0, 1\} ^* $ je libovolný problém, který patří do NP, ukážeme, že $ A ≤_m^p KACHL $. Podle definice NP-úplného problému to bude znamenat, že $ KACHL $ je NP-těžký, a protože patří do NP, tak i NP-úplný problém. To, že $ A ∈ NP $ znamená, že existuje NTS $ M $, který přijímá $ A $ (tj. $ A = L(M) $), a počet kroků každého přijímajícího výpočtu je omezen polynomem $ p(n) $, bez újmy na obecnosti můžeme předpokládat, že $ p(n) ≥ n $, v opačném případě by M nepřečetl ani celý svůj vstup a pokud by platilo, že $ p(n) ≤ n $, stačí vzít $ max(p(n), n) $ místo $ p(n) $. Připomeňme si, že podle definice $ x ∈ A $, právě když existuje přijímající výpočet NTS M nad vstupem x, který má délku nejvýš $ p(|x|) $. Nechť $ M = (Q, Σ, δ, q_0, F ) $, kde $ Q $ obsahuje stavy $ q_0 $ a $ q_1 $ a $ \{0, 1, λ\} ⊆ Σ $. Abychom si zjednodušili situaci, budeme předpokládat, že $ M $ splňuje následující předpoklady:

  1. $ F = \{q_1\} $, tj. $ M $ má jediný přijímající stav $ q_1 $ různý od $ q_0 $.
  2. Pro každé $ a ∈ Σ $ je $ δ(q_1, a) = ∅ $, tj. z přijímajícího stavu neexistuje definovaný přechod.
  3. V počáteční konfiguraci hlava stojí na nejlevějším symbolu vstupního slova $ x $, které je zapsáno počínaje od levého okraje vymezeného prostoru délky $ p(|x|) $. Zbytek pásky je prázdný.
  4. Během výpočtu se hlava $ M $ nepohne nalevo od místa, kde byla v počáteční konfiguraci.
  5. Přijímající konfigurace je daná jednoznačně a vypadá tak, že páska je prázdná a hlava stojí na nejlevější pozici vymezeného prostoru. To odpovídá tomu, že než se $ M $ rozhodne přijmout, smaže nejprve obsah pásky a přesune hlavu k levému okraji vymezeného prostoru.

Není těžké ukázat, že ke každému NTS $ M_1 $ lze zkonstruovat NTS $ M_2 $, který přijímá týž jazyk jako $ M_1 $, „dělá totéž“ a splňuje uvedené podmínky . Většinu zmíněných předpokladů jsme již dříve použili, například při konstrukci univerzálního TS. Bez újmy na obecnosti tedy můžeme předpokládat, že $ M $ splňuje uvedené podmínky. Nechť $ x $ je instance problému $ A $, popíšeme, jak z $ M $, polynomu $ p $ a instance $ x $ vytvořit instanci Kachlíkování, pro kterou bude platit, že v ní existuje přípustné vykachlíkování, právě když existuje přijímající výpočet $ M(x) $, tj. $ M(x) $ přijme. Idea důkazu je taková, že hrany barev mezi dvěma řádky kachlíků budou kódovat konfigurace výpočtu NTS $ M $ nad vstupem $ x $. Vhodným výběrem kachlíků zabezpečíme, že v přípustném vykachlíkování bude řada kachlíků simulovat změnu konfigurace na následující pomocí přechodové funkce. Položíme tedy $ B = Σ ∪ (Q × Σ) ∪ \{q_L, q_R | q ∈ Q\} $. Zatímco vstupní abecedou stroje $ M $ je jen $ \{0, 1, λ\} $, neboť $ x $ musí být binární řetězec, pracovní abecedu stroje $ M $ nijak neomezujeme, a proto zde používáme obecnou abecedu $ Σ $, přičemž předpokládáme, že $ λ ∈ Σ $.

Kachl0.png Vypocet.jpg $ \stackrel{odpovídá}{\Rightarrow} $ Kachl.png

Přehled převodu obecného problému $ A ∈ NP $ na problém $ KACHL $. Horní hrana čtvercové sítě je obarvena počáteční konfigurací, spodní hrana přijímající konfigurací, boky jsou obarveny symbolem $ λ $. Pro ukázku je zde řádek kachlíků s provedením instrukce $ (q’, b, R) ∈ δ(q, a) $, dva kachlíky slouží k provedení instrukce, na ostatních místech je jen kopírovací kachlík pro okopírování barev na další řádek. Po ukončení výpočtu je dokopírována přijímající konfigurace až ke spodní hraně čtvercové sítě.

NP-úplnost SAT (z KACHL)[editovat | editovat zdroj]

diagram sekvence převodů používaných v tomto předmětu
Literál je buď proměnná nebo její negace.
Pozitivní literál je každá proměnná $ x $ .
Negativní literál je každá negace proměnnej $ \overline x $.
Klauzule je disjunkcí literálů, která neobsahuje dva literály s touž proměnnou $ x ∨ \overline y ∨ \overline z $.
Formule $ φ $ je v konjunktivně normální formě (KNF), pokud je konjunkcí klauzulí $ (x ∨ y) ∧ \overline z $.
Je-li $ φ $ formulí na n proměnných a $ t ∈ \{0, 1\}^n $ , pak $ φ(t) $ značí hodnotu $ φ $ v ohodnocení $ t $.

Splnitelnost formule v KNF (SAT)

  • Instance: Formule $ φ $ na $ n $ proměnných v KNF
  • Otázka: ohodnocení, pro které je $ φ $ splněná?

Důkaz transformací KACHL ∝ SAT: pomocí proměnných $ x_{ijk} $, kde $ x_{ijk} = 1 $, pokud na pozici $ [i,j] $ se nachází kachlík typu $ k $. Jednotlivé klauzule se vytvoří tak, aby zaručovaly, že na každé pozici je právě jeden kachlík, že kachlíky navazují horizontálně, vertikálně i na kraje stěny.

Věta ( NP-úplnost SAT ) SAT je NP-úplný problém

Dk($ SAT∈ NP $)

To, že $ SAT $ patří do NP, plyne z toho, že pokud dostaneme vektor $ t ∈ {0, 1}^n $, můžeme spočítat hodnotu φ(t) v polynomiálním čase. Certifikátem kladné odpovědi je tedy splňující ohodnocení. Toto ohodnocení je ve skutečnosti řešením úlohy splnitelnosti, v níž chceme splňující ohodnocení nalézt a ne jen zjistit, zda existuje, tato úloha tedy patří do NPF.

Dk($ SAT∈ NPC \Leftarrow KACHL \leq_m^p SAT $ - neformální konstrukce SAT ze KACHL, zde je formálnější přepis ze skript)
pomocí proměnných $ x_{ijk} $, kde $ x_{ijk} = 1 $, pokud na pozici $ [i,j] $ se nachází kachlík typu $ k $. Jednotlivé klauzule se vytvoří tak, aby zaručovaly, že na každé pozici je právě jeden kachlík, že kachlíky navazují horizontálně, vertikálně i na kraje stěny:
  1. Políčku $ S[i, j] $ přiřadíme !1 typ kachlíku:
    $ β_{i, j} = C_{i, j} ∧ α_{i, j} $ pro $ i, j = 1, . . . , s $.
    Políčku $ S[i, j] $ přiřazen alespoň 1 typ kachlíku:
    $ C_{i, j} = ∨_{k = 1}^{|K|} x_{i, j, k} $
    Políčku $ S[i, j] $ přiřazen nejvýš 1 typ kachlíku:
    $ α_{i, j} = ∧_{k = 1}^{|K|} ∧_{l = k + 1}^{|K|}(\overline x_{i, j, k} ∨ \overline x_{i, j, l}) $
  2. Nad sebou umístěným políčkům $ S[i, j] $ a $ S[(i + 1), j] $ nejsou přiřazeny nekompatibilní typy kachlíků:
    $ γ_{i, j} = ∧ _{(p, q) ∈ V} \overline x_{i, j,p} ∨ \overline x_{(i + 1), j, q} $ pro $ { 1 ≤ i ≤ (s – 1) }, { 1 ≤ j ≤ s } $.
    Vedle sebe umístěným políčkům $ S[i, j] $ a $ S[i, (j + 1)] $ nejsou přiřazeny nekompatibilní typy kachlíků:
    $ δ_{i, j} = ∧_{ (p, q) ∈ H} \overline x_{i, j,p} ∨ \overline x_{i, (j + 1), q} $ pro $ { 1 ≤ i ≤ s } $, $ { 1 ≤ j ≤ (s – 1) } $.
  3. podmínky pro stěny:
Definujeme: $ ε_u = ∧_{j = 1}^s [ ∨_{k ∈ U_j} (x_{1, j, k})] $. Formule $ ε_u $ je splněna, pokud je na každém políčku v prvním řádku kachlík s barvou shodnou s příslušným horním okrajem.
Definujeme: $ ε_b = ∧_{j = 1}^s [ ∨_{k ∈ B_j} (x_{s, j, k)}] $. Formule $ ε_b $ je splněna, pokud je na každém políčku v nejspodnějším řádku kachlík s barvou shodnou s příslušným spodním okrajem.
Definujeme: $ ε_l = ∧_{j = 1}^s [ ∨_{k ∈ L_i} (x_{i, 1, k)}] $. Formule $ ε_l $ je splněna, pokud je na každém políčku v nejlevějším sloupci kachlík s barvou shodnou s příslušným levým okrajem.
Definujeme: $ ε_r = ∧_{j = 1}^s ( ∨_{k ∈ R_i} (x_{i, s, k)}) $. Formule $ ε_l $ je splněna, pokud je na každém políčku v nejlevějším sloupci kachlík s barvou shodnou s příslušným levým okrajem.

S pomocí výše definovaných formulí nyní definujeme formuli $ φ $ jako:

$ φ = [∧_{i = 1}^s ∧_{j = 1}^s β_{i, j}] ∧ [∧_{i = 1}^{(s - 1)} ∧_{j = 1}^s γ_{i, j}] ∧ [∧_{i = 1}^s ∧_{j = 1}^{(s - 1)} δ_{i,j}] ∧ ε_u ∧ ε_b ∧ ε_l ∧ ε_r $.

Z konstrukce okamžitě vyplývá, že $ φ $ je formule v KNF a že velikost $ φ $ je polynomiální v s a $ |K| $, a v polynomiálním čase lze $ φ $ i zkonstruovat.


další zdroje  


NP-úplnost 3-SAT (z SAT)[editovat | editovat zdroj]

input
output

Kubická CNF (vždy jen 3 proměnné v jedné disjunkci) $ F $ na $ n $ Booleovských proměnných. Existuje pravdivostní ohodnocení proměnných, které splňuje formuli $ F $?

Splnitelnost formule v 3KNF (3SAT)

  • Instance: Formule φ na n proměnných v 3KNF, tj. KNF, v níž každá klauzule obsahuje !3 literály.
  • Otázka: ∃ ohodnocení, pro které je φ splněná?

Věta ( NP-úplnost SAT ) SAT je NP-úplný problém.

💡 3SAT není náhodní problém, analogicky definován 2SAT je již polynomiálně řešitelný
Dk ( $ 3SAT\in NP $ )
Problém 3SAT je jen zvláštním případem problému SAT a z téhož důvodu jako v případě problému SAT, patří i 3SAT do třídy NP.
Dk ( $ 3SAT\in NPC \Leftarrow SAT\leq_m^p 3SAT $ )
konstrukce 3SAT $ φ $ z SAT fle $ ψ = C_1 ∧ . . . ∧ C_m $ (kde klauzule $ C_j = (e_1 ∨ . . . ∨ e_k) $ )
SAT klauzule se transformují na 3SAT případně doplní novými proměnnými nastavenými tak aby neovlivňovaly výsledek:
( k = 1 ) $ α_j = (e_1 ∨ y_1^j ∨ y_2^j) ∧ (e_1 ∨ \overline y_1^j ∨ y_2^j) ∧ (e_1 ∨ y_1^j ∨ \overline y_2^j) ∧ (e1 ∨ \overline y_1^j ∨ \overline y_2^j) $
$ y_1^j, y_2^j $ - nové proměnné, které se nevyskytují v ψ
( k = 2 ) $ α_j = (e_1 ∨ e_2 ∨ y^j ) ∧ (e_1 ∨ e_2 ∨ \overline y^j ) $.
( k = 3 ) $ α_j = C_j $
( k > 3 ) $ α_j = (e_1 ∨ e_2 ∨ y_1^j) ∧ (\overline y_1^j ∨ e3 ∨ y_2^j) ∧ (\overline y_2^j ∨ e4 ∨ y_3^j) ∧ . . . ∧ (\overline y_{k−3}^j ∨ e_{k−1} ∨ e_k) $.
Formule 3SAT : $ φ = ∧_{j=1}^m α_j $ a lze ji i v polynomiálním čase zkonstruovat.
SAT $ ψ $ splnitelná ⇔ 3SAT $ φ $ splnitelná (z konstrukce).
Tato část je neúplná a potřebuje rozšířit. doplnit dukaz ekvivalence - u zkousky se vyzaduje


NP-úplnost VP (z 3-SAT)[editovat | editovat zdroj]

input
output

Vrcholové pokrytí (VP - Vertex Cover)

  • Instance: Graf $ G=(V, E) $ a přirozené číslo $ k $
  • Otázka: $ ∃S ⊆ V $ , $ |S| ≤ k $ a z každé hrany obsahuje alespoň jeden vrchol?

Věta ( $ VC ∈ NPC $ ) $ VP $ je NP-úplný problém.

Dk ($ VP ∈ NP $)
pro danou množinu $ S $ dokážeme ověřit v polynomiálním čase, jde-li o VP správné velikosti
Dk ($ VP ∈ NPC $ - $ 3SAT\leq_m^p VP $ )
3SAT: $ φ=C_1∧...∧C_m $ s proměnnými $ U={u_1,...,u_n} $
Konstrukce grafu $ G=(V,E) $ skrz pospojování podgrafů:
$ ∀u_i: $ def.podgraf $ T_i =(V_i, E_i)=(\{u_i, \overline u_i\}, \{ \{u_i, \overline u_i\} \}) $: - VP musí použít vždy aspoň 1 vrchol
$ ∀C_j $: def.trojůhelník $ R_j =(V’_j, E’_j) $: - VP musí použít vždy aspoň 2 vrcholy
podgrafy pospojujeme podle formule $ φ $

Vp.png

$ G $$ VP $ $ |S| ≤ k ⇔ φ $ splnitelná
$ ⇒ k = n + 2m $
VP pokrývá vždy 2 vrcholy z $ R_j $, ex. 1 co není v $ S $ => odp vrchol v $ T_i $ musí být v $ S $ => odpovídajicí proměnná v $ T_i $ musí být true
$ ⇐ $ do $ S $ patří ohodnocené $ u_i / \overline u_i $ ($ n $ vrcholů)
mezi vrcholy z $ R_j $ musí být aspoň 1 pokrytý vrcholem z $ S $
⇒ do $ S $ přidáme ty ostatní 2


NP-úplnost 3DM (z SAT)[editovat | editovat zdroj]

Trojrozměrné párování (3-dimensional matching - 3DM)

  • Instance: Množina $ M⊆ W\times X\times Y $, kde $ W, X, Y $ jsou po dvou disjunktní množiny a $ |W|= |X|= |Y| = q $.
  • Otázka: Obsahuje $ M $ perfektní párování? Jinými slovy, existuje množina $ M'⊆ M $, $ |M'| = q $, trojice v níž obsažené jsou po dvou disjunktní?
Ukázka množin $ T_i^t $ (černě) a $ T_i^f $ (červeně) pro případ $ m=4 $.

Věta ( 3DM ∈ NPC ) 3DM je NP-úplný problém.

Dk($ 3DM ∈ NP $)
plyne z toho, že pokud máme k dispozici množinu $ M'⊆ M $, dokážeme ověřit v polynomiálním čase, jde-li o párování velikosti $ |M'| = q $.


Dk($ 3DM ∈ NPC \Leftarrow SAT\leq_m^p 3DM $ - neformální konstrukce 3DM ze SAT, zde je formálnější přepis ze skript)
Nechť $ \varphi=C_1\wedge C_2\wedge\dots\wedge C_m $ je formule (z klauzulí $ C_i $) v KNF na proměnných $ U=\{u_1, \dots, u_n\} $.
  • Komponenta pro proměnné (truth-setting) - bude určovat, jakou hodnotu která proměnná dostane
∀ proměnnou $ u_i $, $ i=1, \dots, n $ přidáme nové vnitřní prvky $ a_i[1], \dots, a_i[m]∈X $ a $ b_i[1], \dots, b_i[m]∈Y $ a $ u_i[1], \dots, u_i[m], \overline u_i[1], \dots, \overline u_i[m]∈W $.
Na těchto prvcích vytvoříme množiny trojic $ T_i^f $ a $ T_i^t $ takto (viz také obrázek).
PP $ M' $ buď musí obsahovat všechny trojice z $ T_i^t $ (vynucuje TRUE pro proměnnou), nebo všechny trojice z $ T_i^f $ (vynucuje FALSE pro proměnnou).
Převod klauzule $ C_j = (u_1 ∨ ¬u_2 ∨ ¬u_3) $ do trojic v množiny $ S_j $.
  • Komponenta pro klauzule (clause satisfaction testing) - bude zajišťovat propojení hodnoty proměnné s jejími klauzulemi
∀ klauzuli $ C_j $ přidáme nové prvky $ s_1[j]∈X $ a $ s_2[j]∈Y $ a množinu trojic $ S_j $.
Prvky $ s_1[j] $ a $ s_2[j] $ se opět nebudou vyskytovat v jiných trojicích, díky tomu v PP $ M' $ musí být !1 trojice z množiny $ S_j $.
Pokud je $ (u_i[j], s_1[j], s_2[j]) $ v perfektním párování ⇒ v PP $ M' $ je celá $ T^t_i $ (podobně pro negaci).
Doplňující prvky $ g_1[k] $ a $ g_2[k] $
  • Komponenta pro doplnění trojic (garbage collection) - abychom dostali k splňujícímu ohodnocení skutečně PP a naopak
Těmito trojicemi jsme ale schopni v PP pokrýt jen $ mn+n $ prvků z $ 2mn $ prvků $ u_i[j], \overline u_i[j] $, $ i=1, \dots, n $, $ j=1, \dots, m $. Z toho $ mn $ jich pokryjeme trojicemi z $ T_i^t $ nebo $ T_i^f $, $ i=1, \dots, n $. Trojicemi z $ S_j $, $ j=1, \dots, m $ pokryjeme dalších $ m $ prvků.
Zbývá tedy $ 2mn-(mn+m)=m(n-1) $ prvků, jež nejsme zatím schopni pokrýt, proto přidáme do množiny $ M $ trojice, které nám jejich pokrytí zabezpečí.
Do $ X $ přidáme prvky $ g_1[k] $ a do $ Y $ prvky $ g_2[k] $ obojí pro $ k=1, \dots, m(n-1) $ a do $ M $ přidáme množinu trojic
$ G=\{(u_i[j], g_1[k], g_2[k]), (\overline u_i[j], g_1[k], g_2[k])\;|\;1\leq k\leq m(n-1), 1\leq i\leq n, 1\leq j\leq m\} $
Zřejmě platí, že $ M\subseteq W\times X\times Y $ a $ |W|=|X|=|Y|=2mn=q $.
Velikost takto vytvořené instance trojrozměrného párování je tedy polynomiálně velká a v polynomiálním čase ji zřejmě lze i vytvořit.


další zdroje  



LOUP ∈ NPC (z 3DM)[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • Ten převod jsem napsal na 5 stránek (ale mám velké písmo), s tím že některé věci jsem vůbec nerozepisoval, a PK si to prohlídnul (na 5. stranu ani nekouk) a že dobrý, a že mu nemusíme psát romány, že stačí stručně, aby viděl, že to umíme, a že se případně dozeptá. No - jak je koho ctěná libost, ale když toho napíšete hodně, tak se asi na nic už dozeptávat nebude, takže pokud budete mít něco obsáhlého (jako jsem měl já) a napíšete všechno co víte a šikovně vynecháte to co nevíte, tak už toho co víte bude tolik, že na to co nevíte se vás nejspíš už nikdo ptát nebude (teda pokud to nebude něco zásadního - ale i tak to stačí napsat tak stručně, aby to ještě byla pravda a zároveň to ta nechybělo úplně).


input
output

Loupežníci (LOUP) anglicky Partition

  • Instance: Množina $ A $ a váha $ ∀a∈A: s(a)∈N $
  • Otázka: Lze rozdělit prvky z $ A $ na dvě poloviny se stejnou váhou? $ (\sum_{a\in A'}s(a)=\sum_{a\in A\setminus A'}s(a)\;) $

💡 Je zvláště vhodný pro dokazování NP-úplnosti problémů obsahujících numerické paramaetry jako jsou: délky, šířky, ceny, kapacity, atd.

Věta ( LOUP ∈ NPC ) LOUP je NP-úplný problém.

Dk ($ LOUP ∈ NP $)
plyne z toho, že pro zadanou množinu $ A’ ⊆ A $ se ověří v polynomiálním čase, zda obsahuje prvky poloviční ceny.
Dk ($ LOUP ∈ NPC $ - $ 3DM\leq_m^p LOUP $ )
Konstrukce instance LOUP:
Trojrozměrné párování (3-dimensional matching - 3DM)
  • Instance: Množina $ M⊆ W\times X\times Y $, kde $ W, X, Y $ jsou po dvou disjunktní množiny a $ |W|= |X|= |Y| = q $.
  • Otázka: Obsahuje $ M $ perfektní párování? Jinými slovy, existuje množina $ M'⊆ M $, $ |M'| = q $, trojice v níž obsažené jsou po dvou disjunktní?
z kontruujeme LOUP množinu takto $ A={m_1,..,m_k,b_1,b_2} $ (💡 použijeme tedy trojice $ m_i∈M $ a pomocné prvky $ b_1,b_2 $)
cenu prvku $ m_i $ si reprezentujeme jako binární "segmentové číslo" v $ 3q $ blocích, definovaných podle složení trojice $ m_i $
  • $ m_i = {w_{f(i)}, x_{g(i)}, y_{h(i)}} $ kde fce $ f,g,h $ vrací odpovídající indexy prvků z trojice $ m_i $
  • ∀ blok (z segmentu) má $ p = ⌈log_2(k + 1)⌉ $ bitů
  • pokud je prvkem trojice nastaví se v bloku bit na 1 zprava (ten nejméně významny) a ostatní na 0 (tedy formálně: $ s(a_i)=2^{p(3q-f(i))}+2^{p(2q-g(i))}+2^{p(q-h(i))} $)
  • počet bitů pro reprezentaci $ s(a_i) $ je $ 3pq $ (polynomiální) ⇒ 💡 ceny $ s(a_i) $ se dají zkontruovat v polynomiálním čase
dále si vytvoříme stejné segmentové číslo $ B $ s 1 zprava v ∀ bloku (tedy $ B=\sum_{j=0}^{3q-1}2^{pj} $)
Popis $ 3q $ segmentů, ∀ obsahuje $ p = ⌈log_2(k + 1)⌉ $ bitů binární reprezentace $ s(a) $, použité pro převod 3DM na LOUP.
teď dokážeme že $ A'\subseteq\{a_i\;|\;1\leq i\leq k\}: B=∑_{a_i∈A’} s(a_i) ⇔ M’=\{m_i|a_i∈A’ \} $ je 3DM
určíme si poslední dva pomocné dva prvky z $ A $:
$ s(b_1) = 2∑s(a_i) - B $
$ s(b_2) = ∑s(a_i) + B $
celkem pro množ. $ A $ tedy máme $ ∑s(a_i) + s(b_1) + s(b_2) = ∑s(a_i) + 2∑s(a_i) - B + ∑s(a_i) + B = 4∑s(a_i) $
pokud $ A'\subseteq A: \sum_{a\in A'}s(a)=\sum_{a\in A\setminus A'}s(a) = 2∑s(a_i) $
$ b_1,b_2 $ nemůžou být oba ani v jedné půlce
$ \sum_{A'\setminus \{b_1\}}s(a) =B $ (💡 musí být po řádcích disjunktní jinak by nám nevyšlo $ B $) a $ A’\setminus \{b_1\} $ určují perfektní párování v $ M $ (=$ 3DM $)
nyní definujme 3DM $ M'⊆M $ a $ A’=\{a_i|m_i∈M’ \} $
$ ∑_{a\in A'}s(a) + s(b_1) = 2∑s(a_i) $
$ A’\cup \{b_1\} $ tedy obsahuje prvky poloviční ceny (=$ LOUP $)


Pseudopolyn. alg., číselné probl. a silná NPC. Př. pseudopolyn. alg. Batoh (🎓)[editovat | editovat zdroj]

Pseudopolynomiální algoritmy, číselné problémy a silná NP-úplnost. Příklad pseudopolynomiálního algoritmu pro Batoh

Zážitky ze zkoušek  
  • pseudopolynomialni algoritmy - formalni definice pseudopolynomialniho algoritmu, silne NPU problem. Algoritmus reseni SP. Priklad silne NPU (TSP s omezenim na vaze hran) a proc je silne NPU (prevod na HK). Nekolik otazek jak souvisi pseudopolynomialni algoritmy a aproximacni algoritmy.
  • Definice len, max, číselnosti, NP-úplnosti, pseudopoly alg., silné NP-úplnosti (napsal jsem bez kvantifikátorů a tedy jsem je musel doplnit). Příklad silně NP-úplného (obchodní cestující) a slabě (součet podmnožiny, loupežníci). Pak padl dotaz k čemu je možné pseudopoly alg. využít - základ pro aproximační schémata.
  • Definice obojiho, jedna veticka o tom, ze silne NP-uplne nemaji pseudopol. alg., strucne napsany pseudopol. problem pro batoh, veta o tom, ze pokud bychom nasli pro silne NP-uplny problem pseudopolynamialni alg., muselo by platit, ze $ P=NP $. Nic dalsiho nebylo potreba vedet.
  • Napsal jsem špatnou definici pseudopolynomiálních algoritmů, aproximací, AS, a ÚPAS. Na dotaz jestli znám nějaké AS jsem zmínil ÚPAS pro SP, a to že patrně obsahuje nějakou proceduru co cosi prořezává. Posléze se mi podařilo přijít na správnou definici pseudopolynomiálních algoritmů, a to jak by zhruba měl vypadat pseudopolynomiální algoritmus pro problém batohu. Tou dobou ale už všichni ze zkoušky odešli tak mě nechal jít :-)


Číselný problém je rozhodovací problém $ A $, pokud pro každý polynom p existuje instance $ I $ problému $ A $, pro kterou platí, že $ max(I) > p(len(I)) $.

  • len(I) - délka binárního zakódování instance I
  • max(I) - hodnota největšího zadaného čísla v instanci I (je obsaženo ve vstupu)
💡 Pro Batoh je $ len(I) = O(n log_2(B + V)) $, ale $ max(I) = max(\{B\} ∪ \{v[i], s[i] | 1 ≤ i ≤ n\}) $. Například LOUP nebo Batoh jsou tedy číselné problémy, zatímco SAT nebo KLIKA číselné problémy nejsou.
  • Algoritmus řešící $ A $ je pseudopolynomiální , pokud je jeho časová složitost omezená polynomem dvou proměnných $ max(I) $ a $ len(I) $.
💡 Alg. pro Batoh je pseudopolynomiální (viz níže). Je-li problém $ A $ řešitelný pseudopolynomiálním algoritmem a není-li $ A $ číselný problém, pak je zřejmě tento pseudopolynomiální algoritmus ve skutečnosti polynomiální. Pokud bychom tedy pro nějaký nečíselný NP-úplný problém (např. kliku nebo SAT) našli pseudopolynomiální algoritmus, znamenalo by to, že $ P = NP $.

NP-úplný problém, pro který ∃ pseudopolynomiální alg., nazýváme slabě NP-úplný.

Pokud ∄ pseudopolynomiální alg. je silně NP-úplný (💡 pokud P ≠ NP). Silná/slabá NP-těžkost se definuje analogicky.

Formálně: $ p $ je polynom a $ A $ NP-úplný problém:

  • $ A(p) $ je restrikce problému $ A $ na instance $ I $ s $ max(I) ≤ p(len(I)) $.
  • Silně NP-úplný je problém $ A $, pokud ∃ polynom $ p $, pro nějž je problém $ A(p) $ NP-úplný.
  • Slabě NP-úplný je problém $ A $, pokud ∄ polynom $ p $, pro nejž je problém $ A(p) $ NP-úplný.

Věta ( OC je silně NP-úplný ) Problém Obchodního cestujícího je silně NP-úplný.

Dk
💡 $ max(I) $ je v tomto případě největší vzdálenost mezi městy
v grafu ex. Hamiltonovská kružnice <=> OC obejde všechny města a vzdálenost mezi městy je vždy 1
OC(1) je stále NP-úplný => OC je silně NP-úplný
0/1 knapsack problem (💡 0/1 = buď předmět vezmu nebo ne)

Příklad pseudopolynomiálního algoritmu pro Batoh[editovat | editovat zdroj]

Batoh ( 0/1 knapsack problem ), úloha
  • Instance : Množina n předmětů $ A = {a_1, . . . , a_n} $, s každým předmětem velikost $ s(a_i) ∈ N $ a cena či hodnota $ v(a_i) ∈ N $. Přirozené číslo $ B ≥ 0 $ udávající velikost batohu.
  • Cíl : Nalézt množinu předmětů $ A‘ ⊆ A $, která dosahuje maximální souhrnné hodnoty předmětů v ní obsažených, a přitom se předměty z $ A $ vejdou do batohu velikosti $ B $.
Pseudopolynomiální alg. $ Batoh(s, v, B) $ (💡 bottom-up dynamické programování)
  • Vstup : Pole velikostí(size) $ s $, cen (value) předmětů $ v $ ($ |s|=|v|=n $) a velikost batohu $ B $. Platí: $ 0 < s[i] ≤ B $.
  • Výstup : Mnž. $ |M|≤ B $ a s maximální cenou.
  • Prerekvizity : $ V $ je suma cen všech předmětů ($ V= Σ_{i = 1^n} v_i $).
Nechť $ T $ je tabulka $ (n + 1) × (V + 1) $, na pozici $ T [j, c] $ ( $ 0 ≤ j ≤ n , 0 ≤ c ≤ V $ ), bude podmnožina indexů ( $ 1, . . . , j $ ) prvků celkové ceny přesně $ c $ s minimální velikostí.
Nechť $ S $ je tabulka $ (n + 1) × (V + 1) $, na pozici $ S[j, c] $ je celková velikost předmětů v množině $ T [j, c] $. Pokud neexistuje množina s předměty ceny přesně $ c $, je na pozici $ S[j, c] $ číslo $ B + 1 $.
běh alg. $ Batoh(s, v, B) $, barvy ukazují jak vznikaly množiny (pokud se jen nekopírovaly z minulého kroku cyklu přes předměty), šipky ukazují směr průchodu alg. tabulkou (bottom-up)
Batoh(s, v, B):
 0: # Inicializace tabulek:
 1: for (c = 0 to V) {
 2:   T[0, c] = ∅; # temp
 3:   S[0, c] = B + 1; # sums of sizes
 4: }
 5: S[0, 0] = 0;
 6: # Cyklus přes všechny předměty:
 7: for (j = 1 to n) {
 8:   T[j, 0] = ∅;
 9:   S[j, 0] = 0;
10:   # Cyklus zvyšující cenový limit:
11:   for (c = 1 to V) 
12:     if (v[j] ≤ c) && # zda předmět j může být součástí řešení
13:        (S[j – 1, c] > S[j - 1, c - v[j]] + s[j]) { # minimalizujeme celkovou velikost předmětů při zachování c
14:       S[j, c] = S[j – 1, c − v[j]] + s[j];
15:       T[j, c] = T[j – 1, c − v[j]] ∪ {j};
16:     } else {
17:       S[j, c] = S[j – 1, c];
18:       T[j, c] = T[j – 1, c];
19:     }
20: }
21: c = max{c| S[n, c] ≤ B};
22: return T[n, c];

💡 Kučerova verze algoritmu MINImalizuje celkovou velikost předmětů (při zachování celkové ceny), běžné verze např. na wikipedii MAXImalizují celkovou cenu (při zachování celkové velikosti předmětů)

Věta ( Batoh v čase $ O(nV) $ ) Algoritmus Batoh nalezne pro zadaný vstup množinu předmětů s nejvyšší cenou, jež se vejdou do batohu velikosti $ B $. Pracuje v čase $ O(nV) $.

Dk ($ O(nV) $)
Kroky 0 až 6 zvládneme jistě v čase $ O(nV) $, uvažujeme-li aritmetické operace jako konstantní. Následují dva vnořené cykly v rámci nichž jsou použity aritmetické operace, na něž stačí konstantní čas. I řádek 14 lze provést v konstantním čase při vhodné reprezentaci množin v $ T [j, c] $. Můžeme například použít reprezentaci pomocí bitového pole délky n, nebo pomocí spojového seznamu, v obou případech je přidání prvku do množiny jednoduché.
Dk (korektnost indukcí)
Ukážeme, že na konci běhu algoritmu splňují tabulky T a S vlastnosti, jež jsme popsali v prerekvizitách algoritmu. Jmenovitě ukážeme, že:
  1. Na pozici $ T [j, c] $, $ 0 ≤ j ≤ n, 0 ≤ c ≤ V $ je po ukončení algoritmu podmnožina $ \{1, . . . , j\} $ prvků celkové ceny přesně $ c $ s minimální velikostí mezi všemi takovými množinami. Pokud neexistuje množina prvků s cenou přesně $ c $, pak na pozici $ T [j, c] $ bude ∅.
  2. Na pozici $ S[j, c] $, $ 0 ≤ j ≤ n, 0 ≤ c ≤ V $ je po ukončení algoritmu součet velikostí prvků v množině na pozici $ T [j, c] $. Pokud neexistuje množina prvků s cenou přesně $ c $, pak na pozici $ S[j, c] $ je $ (B + 1) $.
Tyto vlastnosti ukážeme indukcí podle $ j $.
Na začátku vyplníme nultý řádek v cyklu na řádcích 1 až 4, pro $ j = 0 $ tedy vlastnosti (1.) a (2.) platí.
Nyní předpokládejme, že vlastnosti (1.) a (2.) platí pro řádky $ 0, . . ., (j – 1) $ a ukažme, že platí i pro $ j $-tý řádek.
$ T [j, 0]=∅ $ protože je to nejmenší množina prvků s cenou $ 0 $. Takto provedeme nastavení $ T[j, 0] $ a $ S[j, 0] $ na řádcích 8 a 9.
Pokud je $ c > 0 $, pak na ně narazíme na vhodném místě v rámci vnitřního cyklu.
Pro $ j > 0 $ a $ c > 0 $ máme dvě možnosti, buď v nejmenší množině prvků $ {1, . . . , j} $ s cenou $ c $ není prvek $ j $, potom se jedná o množinu uloženou podle indukční hypotézy na pozici $ T[j − 1, c] $, nebo se v této množině prvek $ j $ vyskytuje. Pokud bychom z této nejmenší množiny prvek odstranili, museli bychom dostat nejmenší množinu s cenou ($ c − v[j]) $ z prvků $ \{1, . . . , (j – 1)\} $, která je podle indukčního předpokladu uložena na pozici $ T [j – 1, c − v[j]] $.
Z těchto dvou možností vybereme tu, která má menší velikost. Díky tomu také na pozici $ T [j, c] $ uložíme ∅ a na pozici $ S[j, c] $ hodnotu $ (B + 1) $ jedině tehdy, pokud obě množiny na pozicích $ T [j − 1, c] $ a $ T [j − 1, c − v[j]] $ jsou ∅ a obě odpovídající velikosti jsou $ (B + 1) $.
Zde využíváme toho, že porovnávání v kroku 13 je ostré, a tedy k přiřazení v kroku 14 dojde jedině tehdy, když je množina na pozici $ T [j − 1, c − v[j]] $ neprázdná, jinak by z ∅ přidáním prvku $ j $ vznikla množina neprázdná.
Na závěr tedy při platnosti (1.) a (2.) stačí v kroku 21 vybrat množinu s největší cenou. Množina cen, z nichž vybíráme, je vždy neprázdná, neboť přinejmenším $ S[n, 0] = 0 $.

Aproximační algoritmy - definice a příklad (🎓)[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • Majerech - Aproximační algoritmy a schémata - Definice AA, poměrová a relativní chyba, AS, PAS, ÚPAS, ÚPAS pro SP (pozor na písmena v popisu PROŘEŽ (1-d)z < y < z), AA pro TSP


Optimalizační úloha A je buď maximalizační nebo minimalizační a skládá se z těchto tří částí:

  1. Množina instancí $ D_A ⊆ \{0, 1\}^* $.
  2. Pro každou instanci $ I ∈ D_A $ je dána množina přípustných řešení $ S_A(I) ⊆ \{0, 1\}^* $.
  3. Funkce $ μ_A $, která každé instanci $ I ∈ D_A $ a každému přípustnému řešení $ σ ∈ S_A(I) $ přiřadí kladné racionální číslo $ μ_A(I, σ) $, které nazveme hodnotou řešení σ.
  • Pokud je A maximalizační úlohou, pak optimálním řešením instance $ I ∈ D_A $ je $ σ ∈ S_A(I) $, pro něž je $ μ_A(I, σ) $ maximální (tj. $ μ_A(I, σ) = max\{μ_A(I, σ) | σ ∈ S_A(I)\} $).
    • Pokud je $ A $ minimalizační úlohou, pak optimálním řešením instance $ I ∈ D_A $ je $ σ ∈ S_A(I) $, pro něž je $ μ_A(I, σ) $ minimální (tj. $ μ_A(I, σ) = min\{μ_A(I, σ) | σ ∈ S_A(I)\} $).
    • Hodnotu optimálního řešení instance $ I ∈ D_A $ označujeme $ OPT_A(I)= μ_A(I, σ) $ (kde $ σ $ je optimální řešení intance $ I $).
  • Řekneme, že algoritmus $ ALG $ je aproximačním algoritmem pro optimalizační úlohu $ A $, pokud pro každou instanci $ I ∈ D_A $ vrátí $ ALG $ se vstupem $ I $ řešení $ σ ∈ S_A(I) $, případně ohlásí, že žádné přípustné řešení neexistuje, pokud $ S_A(I) = ∅ $.
  • Hodnotu řešení vráceného algoritmem $ ALG $ na instanci $ I $ označíme jako $ ALG(I) $, tj. $ ALG(I) = μ_A(I, σ) $, kde $ σ ∈ S_A(I) $ je přípustné řešení vrácené algoritmem $ ALG $.
  • Pokud je $ A $ maximalizační úloha, pak racionální číslo $ ε ≥ 1 $ nazveme aproximačním poměrem algoritmu $ ALG $, pokud pro každou instanci $ I ∈ D_A $ platí, že $ OPT (I) ≤ ε.ALG(I) $ .
    • Je-li $ A $ minimalizační úlohou, pak racionální číslo $ ε ≥ 1 $ nazveme aproximačním poměrem algoritmu $ ALG $, pokud pro každou instanci $ I ∈ D_A $ platí, že $ ALG(I) ≤ ε.OPT(I) $ .

Příklad aproximačního algoritmu pro Bin Packing[editovat | editovat zdroj]

Bin Packing – BP, úloha
  • Instance : Konečná množina předmětů $ U = {u_1, .., u_n} $, s každým předmětem asociovaná velikost $ s(u) $, což je racionální číslo, pro které platí $ 0 ≤ s(u) ≤ 1 $.
  • Cíl : Najít rozdělení všech předmětů do co nejmenšího počtu po dvou disjunktních množin $ U_1, . . ., U_m $ takové, že každá množina může mít velikost max 1.
💡 Naším cílem je tedy minimalizovat $ m $.
💡 Formálně je tedy $ D_{BP} $ množinou řetězců kódujících instance $ BP $, pro danou instanci $ I= ⟨U, s(u)⟩ $ je množina $ S_BP(I) $ množinou všech možných rozdělení do dostatečného množství košů. Mírou řešení $ μ_{BP}(σ) $ pro $ σ ∈ S_{BP}(I) $ je počet košů, které řešení využívá, tedy hodnota $ m $. Rozhodovací verze tohoto problému je shodná s problémem Rozvrhování, o jehož těžkosti víme, z toho plyne, že i úloha $ BP $ je $ NP $-těžká. Šance na to, že bychom našli polynomiální algoritmus, řešící $ BP $ přesně, jsou tedy malé.
Algoritmus (First Fit pro Bin Packing – $ FF-BP $)
  • Ber jeden předmět po druhém,
    • ∀ předmět $ u $ najdi první koš, do nějž se tento předmět ještě vejde,
    • pokud takový koš neexistuje, přidej nový koš obsahující jen předmět $ u $.

💡 Algoritmus $ FF-BP $ je zřejmě polynomiální.

Věta ( Aproximační poměr $ FF-BP $ je 2 ) ∀ instanci $ I ∈ DBP $ platí, že $ FF-BP(I) < 2.OPT_{BP}(I) $.

Dk
V řešení, které vrátí $ FF-BP $ je nejvýš jeden koš, který je zaplněn nejvýš z poloviny. Kdyby totiž existovaly dva koše $ U_i $ a $ U_j $ pro $ i < j $, které jsou zaplněny nejvýš z poloviny, tak by $ FF-BP $ nepotřeboval zakládat nový koš pro předměty z $ U_j $, všechny by se vešly do $ U_i $.
Pokud $ FF-BP(I) > 1 $, pak z toho plyne, že: $ FF-BP(I) < ⌈2 Σ_{i = 1}^n s(u_i)⌉ ≤ 2⌈Σ_{i = 1}^n s(u_i)⌉ $, kde první nerovnost plyne z toho, že po zdvojnásobení obsahu jsou všechny koše plné až na jeden, který může být zaplněn jen částečně.
Rovnosti bychom přitom dosáhli jedině ve chvíli, kdy by byly všechny koše zaplněné právě z poloviny, což není podle našeho předpokladu možné.
Druhá nerovnost plyne z vlastností zaokrouhlování.
Na druhou stranu musí platit, že $ OPT(I) ≥ ⌈Σ_{i = 1}^n s(u_i)⌉ $.
Dohromady tedy dostaneme, že $ FF-BP(I) < 2.OPT(I) $. Pokud $ FF-BP(I) = 1 $, pak i $ OPT(I) = 1 $ a i v tomto případě platí ostrá nerovnost.

Lemma Pro libovolnou hodnotu m ∃ instance $ I ∈ D_{BP} $, pro niž je $ OPT(I) ≥ m $ a $ FF-BP(I) ≥ 5/3 \cdot OPT(I) $.

Dk
Instance bude mít $ U = {u_1, u_2, . . . , u_18m} $, s těmito prvky asociujeme váhy takto:
$ 1≤ i ≤ 6m : s(ui) = 1/7 + ε $, $ 6m< j ≤ 12m : s(ui) = 1/3 + ε $, $ 12m< j ≤ 18m : s(ui) = 1/2 + ε $. Kde $ ε > 0 je $ dostatečně malé kladné racionální číslo. Optimální rozdělení rozdělí prvky do $ 6m $ košů, do každého dá po jednom prvku s velikostmi $ (1/7 + ε), (1/3 + ε), (1/2 + ε) $. Hodnotu ε zvolíme dostatečně malou tak, aby se každá z těchto trojic vešla do koše velikosti $ 1 $. Algoritmus $ FF-BP $ bude brát prvky jeden po druhém a vytvoří nejprve m košů, každý s šesti prvky velikosti $ (1/7 + ε) $, přičemž hodnotu $ ε $ zvolíme dostatečně malou na to, aby se tam vešly, ale protože je kladná, nevejde se k nim nic dalšího. Poté vytvoří $ 3m $ košů, každý se dvěma prvky velikosti $ (1/3 + ε) $, k nimž se opět nic nevejde.
Nakonec $ FF-BP $ vytvoří $ 6m $ košů, každý s jedním prvkem velikosti$ (1/3 + ε) $. Dohromady je $ FF-BP(I) = 10m $, a tedy $ [ FF-BP(I) / OPT(I) ] = 5/3 $.
💡 Pochopitelně brát prvky v libovolném pořadí tak, jak to činí $ FF-BP $ je nejhloupější možnou strategií. Na instanci popsanou v důkazu lemmatu by přitom stačilo, kdybychom nejprve prvky $ U $ setřídili sestupně podle velikosti a poté je umísťovali do košů v pořadí od největšího k nejmenšímu. Algoritmus, který postupuje podle této strategie nazveme $ FF-D-BP $ z anglického „decreasing“. Lze ukázat, že pro libovolnou instanci $ I ∈ D_{BP} $ platí: $ FF-D-BP(I) ≤ (11/9).OPT(I) + 4 $.

Aproximační schémata, př. pro Batoh (🎓)[editovat | editovat zdroj]

Aproximační schémata - definice a příklad aproximačního schématu pro Batoh

💡 inkluze tříd NP, APX, PAS, ÚPAS, P a Pseudo-PTIME
Zážitky ze zkoušek  
  • definicia optimalizacnej ulohy, definicia aproximacneho algoritmu, aproximacneho pomeru, aproximacneho schema, PAS a UPAS, schema pre BATOH


Nechť $ A $ je libovolná optimalizační úloha. Algoritmus $ ALG $ nazveme aproximačním schématem pro úlohu $ A $, pokud na vstupu očekává instanci $ I\in D_A $ a racionální číslo $ \varepsilon>0 $ a na výstupu vydá řešení $ \sigma\in S_A(I) $, jehož hodnota se od optimální liší s aproximačním poměrem $ (1+\varepsilon) $.

  • Tj. pro maximalizační úlohu platí, že: $ OPT(I)\leq(1+\varepsilon)ALG(I, \varepsilon) $
  • a pro minimalizační úlohu platí, že: $ ALG(I, \varepsilon)\leq(1+\varepsilon)OPT(I)\;. $

Předpokládejme, že algoritmus $ ALG $ je aproximační schéma a očekává na vstupu instanci $ I\in D_A $ a racionální číslo $ \varepsilon $. Pomocí $ ALG_\varepsilon $ označíme instanci algoritmu $ ALG $, kde hodnota $ \varepsilon $ je zafixována, vstupem $ ALG_\varepsilon $ je tedy jen instance $ I\in D_A $ a běh i výstup $ ALG_\varepsilon $ na vstupu $ I $ jsou totožné s algoritmem $ ALG $ se vstupem $ I $ a $ \varepsilon $.

  • Řekneme, že $ ALG $ je polynomiální aproximační schéma (PAS), pokud je pro každé $ \varepsilon $ časová složitost algoritmu $ ALG_\varepsilon $ polynomiální v $ len(I) $, kde $ ALG_\varepsilon $ označuje algoritmus vzniklý dosazením konstanty $ \varepsilon $ do $ ALG $
  • Řekneme, že $ ALG $ je úplně polynomiální aproximační schéma (ÚPAS), pokud $ ALG $ pracuje v čase polynomiálním v $ len(I) $ a $ \frac{1}{\varepsilon} $.

Věta ( ) Nechť $ A $ je optimalizační úloha, jejíž přípustná řešení mají nezápornou celočíselnou hodnotu. Předpokládejme, že ∃ polynom dvou proměnných $ q $, který pro každou instanci $ I ∈ DA $ splňuje: $ OPT(I) < q(len(I), max(I)) $. Pokud ∃ úplně polynomiální aproximační schéma pro úlohu $ A $, pak ∃ i pseudopolynomiální algoritmus pro $ A $.

💡 Důsledek : Nechť $ A $ je silně NP-úplná optimalizační úloha, která splňuje předpoklady věty. Pokud $ P = NP $, pak neexistuje úplně polynomiální aproximační schéma pro úlohu $ A $.

Věta ( ) Pokud existuje polynomiální aproximační algoritmus $ ALG $ pro úlohu obchodního cestujícího s aproximačním poměrem $ ε $, kde $ ε > 1 $ je konstanta, potom $ P = NP $.

💡 př. použití aprox.schématu: $ I $ je moc složitá pro přímé nalezení $ OPT $, zjednodušíme jí tedy a získáme řešení $ ALG_\varepsilon(I) $ to ještě můžeme přeložit zpět na řešení odpovídající původní instanci $ I $ (u BAPX to ani není nutné)

Příklad aproximačního schématu pro Batoh - BAPX[editovat | editovat zdroj]

  • Vstup: Pole $ s $ velikostí předmětů a pole $ v $ cen předmětů, obě délky $ n $, velikost batohu $ B $, racionální číslo $ \varepsilon>0 $. Předpokládáme, že $ (\forall i\in\{1, \dots, n\})\;\big[0<s[i]\leq B\big] $
  • Otázka: Množina M předmětů, jejichž souhrnná velikost nepřesahuje B.

$ BAPX(s, v, B, \varepsilon) $

  1. Spočti index m, pro nějž je $ v[m] = max_{1\leq i\leq n} v[i] $.
  2. if ($ \varepsilon \geq n - 1 $) return {m}
  3. $ t = ⌊log_2( \varepsilon v[m]/n )⌋ - 1 $
  4. c je nové pole délky n.
  5. for ($ i= 1; i\leq n;i++ $) $ c[i] = ⌊v[i]/2^t⌋ $
  6. return Batoh(s, c, B) // Volání původního algoritmu

💡 algoritmus provede zaokrouhlení cen předmětů a jejich přeškálování podle $ ε $

Věta ( Algoritmus BAPX je $ O(\frac{1}{\varepsilon}n^3) $ ) Schéma BAPX pracuje v čase $ O(\frac{1}{\varepsilon}n^3) $. Pro libovolnou instanci $ I = ⟨s, v, B⟩ $ úlohy Batoh a libovolné $ ε > 0 $ platí, že $ OPT(I) ≤ (1 + ε) BAPX(I, ε) $.

coNP, #P - def. a vlastnosti[editovat | editovat zdroj]

Definice (Nesplnitelnost KNF (UNSAT), úloha):

  • Instance : Formule $ φ $ v KNF
  • Otázka : Platí, že pro každé ohodnocení v je $ φ(v) = 0 $?
  • Poznámka: Nevíme, jak by měl vypadat polynomiálně ověřitelný důkaz toho, že formule $ φ $ je nesplnitelná, ale můžeme najít polynomiálně ověřitelný protipříklad, tedy důkaz toho, že $ φ $ není nesplnitelná { = je splnitelná}, protože $ SAT $ patří do NP.

coNP[editovat | editovat zdroj]

$ coNP $

Jazyk (problém) A ⊆ {0, 1} patří do třídy coNP, pokud jeho doplněk patří do třídy NP.

Jazyk A je co-NP-úplný, je-li $ coNP $ a pro libovolný jiný jazyk $ B ∈ co-NP $ platí, že $ B ≤^m_p A $.

Lemma Jazyk $ A $ je co-NP-úplný ⇔ $ \overline A $ je NP-úplný.

Lemma Patří-li některý NP-úplný jazyk do $ coNP $, pak $ NP=coNP $ { nepředpokladané }.

Lemma $ P ⊆ ( NP ∩ coNP) $ { předpoklad, že $ P ⊊ NP ∩ coNP $ }.

#P[editovat | editovat zdroj]

Funkce $ f $ patří do třídy #P, pokud existuje binární relace $ R $ v NPF a $ \forall x $: $ f(x) = |\{y | (x, y) ∈ R\}| $. Pak $ f $ je početní úlohou asociovanou s $ R $, značíme pomocí $ \#R = f $.

Lemma Pro každý problém $ A ∈ NP $ $ ∃ $ relace $ R_A $ v NPF, tak že platí: $ x ∈ A ⇔ \#RA(x) > 0 $.

Dk
Relace RA bude obsahovat dvojice $ (x, y) $, kde $ y $ je polynomiálně velký certifikát dosvědčující to, že $ x ∈ A $.

Lemma Výpočet $ f ∈ \#P $ lze provést za pomoci polynomiálně mnoha dotazů na náležení prvku do množiny $ \{(x, N) | f(x) ≥ N\} $.

Dk
Protože $ f ∈ \#P $, existuje relace $ R ∈ NPF $, pro kterou platí, že $ f = \#R $. Z definice plyne, že existuje polynom p, pro který platí, že pokud $ (x, y) ∈ R, pak |y| ≤ p(|x|) $. To $ p(|x|) $ znamená, že $ f(x) ≤ 2 $ , pokud uvažujeme $ x $ i $ y $ jako binární řetězce. Binárním vyhledáváním $ p(|x|) $ najdeme hodnotu $ f(x) $ dotazy na $ N = 0, . . . , 2p(|x|) $ , protože binární vyhledávání pracuje v logaritmickém čase, bude nám na toto vyhledání stačit $ p(|x|) $ dotazů, je jich tedy polynomiálně mnoho.

Lemma Výpočet $ f ∈ \#P $, $ f(x) $ lze provést v polynomiálním prostoru vzhledem k $ |x| $.

Dk
Nechť f ∈ #P, podle definice to znamená, že existuje relace R ∈ NPF, pro kterou platí, že f = #R. Z definice plyne, že existuje polynom p, pro který platí, že pokud (x, y) ∈ R,p(|x|) pak |y| ≤ p(|x|), což znamená, že f(x) ≤ 2 , a k reprezentaci hodnoty f(x) nám tedy postačí p(|x|) bitů. Algoritmus počítající f(x) bude postupně generovat všechny binární řetězce y délky nejvýš p(|x|), pro každý z nich ověříme, zda (x, y) ∈ R a pokud ano, zvýšíme hodnotu f o jedna. K ověření (x, y) ∈ R nám podle definice NPF stačí polynomiální čas, a tedy i prostor, pro uložení y i hodnoty f(x) nám také stačí polynomiální prostor, a celkový prostor je tedy polynomiální.

Funkce $ f : \{0, 1\}* → N $ je polynomiálně převoditelná na funkci $ g : \{0, 1\}* → N $, pokud existují polynomiálně spočitatelné funkce $ α : \{0, 1\}* × N → N $ a $ β : \{0, 1\}* → \{0, 1\}* $ , pro které platí, že: $ (∀x ∈ {0, 1} ) [f(x) = α(x, g(β(x)))] $ ( odpovídá polyn. algoritmu, spočítá $ f(x) $ s jedním voláním $ g $ ).

Funkce $ f : \{0, 1\} $ je #P-těžká, pokud je každá funkce $ g ∈ \#P $ polynomiálně převoditelná na $ f $.

Funkce $ f $ je #P-úplná, je-li #P-těžká a platí-li současně, že $ f ∈ \#P $.

Nechť $ A, B ∈ NPF $ jsou binární relace, řekneme, že polynomiálně spočitatelná funkce $ β $ převádí $ A $ na $ B $ se zachováním počtu řešení, pokud $ ∀x ∈ \{0, 1\}* : |\{y | (x, y) ∈ A\}| = |\{y | (β(x), y) ∈ B\}| $.

Lemma Nechť $ A ∈ NPF $ je taková, že libovolnou relaci z NPF lze na $ A $ polynomiálně převést se zachováním počtu řešení, potom #A je #P-úplná úloha.

Poznámky:

  • Například tedy #KACHL, #SAT , #HK, #LOUP a další jsou všechno #P-úplné úlohy { převody, které jsme si ukazovali, lze udělat tak, aby zachovávaly počty řešení, proto lze ukázat, že úlohy odpovídající problémům, jejichž těžkost jsme si ukazovali, jsou #P-úplné }.
  • #SAT je #P-úplná funkce, protože redukce, již jsme si ukazovali pro převod obecného problému z NP na SAT zachovává počty řešení/certifikátů.
  • Podobně to platí o dalších početních funkcích, asociovaných s dalšími NP-úplnými problémy a úlohami, jejichž těžkost jsme si ukazovali { s každým problémem A v NP je asociovaná úloha z NPF, která pro zadaný vstup najde certifikát náležení do A, pokud takový certifikát existuje }.
  • Existují úlohy z PF takové, že s nimi asociované početní funkce jsou #P-úplné.
  • #DNF-SAT je #P-úplná funkce, ačkoli DNF-SAT patří do P.
  • Také určení počtu perfektních párování v bipartitním grafu je #P-úplná funkce, zatímco najít nějaké perfektní párování (pokud existuje) je polynomiálně řešitelná úloha.

Term je konjunkcí literálů, neobsahující dva literály s touž proměnnou.

Formule $ φ $ je v disjunktivně normální formě (DNF), pokud je disjunkcí termů.

Věta ( #DNF-SAT je #P-úplná ) #DNF-SAT je #P-úplná

Prerekvizita – Problém splnitelnosti formule v DNF je polynomiálně řešitelný { DNF-SAT je P }.

Dk
Protože úloha DNF-SAT zřejmě patří do NPF (dokonce do do PF), patří #DNF-SAT do #P. Popíšeme, jak převést #SAT (tj. #KNF-SAT, chceme-li explicitně zdůraznit, že jde o splnitelnost formule v KNF) na #DNF-SAT. Protože #KNF-SAT je #P-úplná funkce, bude to platit i o #DNF-SAT. Nechť $ φ $ je formule v KNF, pomocí de-Morganových pravidel převedeme její negaci $ ¬φ $ na DNF, kterou si označíme pomocí $ ψ ≡ ¬φ $, pak platí, že: $ \#KNF-SAT(φ) = 2n − \#DNF-SAT(ψ) $, kde $ n $ je počet proměnných formule $ φ $. V převodu tedy funkce $ ψ = β(φ) $ spočítá DNF negace zadané formule v KNF a funkce α(φ, c) odečte počet c = #DNF-SAT(ψ) od 2n. To vše lze jistě provést polynomiálně.

Metody tvorby algoritmů: rozděl a panuj, dynamické programování, hladový algoritmus (zkoušková, 🎓)[editovat | editovat zdroj]

Metody tvorby algoritmů: rozděl a panuj, dynamické programování[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • U dynamickýho programování jsem nějak sesmolil princip fungování a napsal jsem tam jeden konkrétní algoritmus (z grafiky - matchování vrcholů dvou mnohoúhelníků), na kterym jsem ukazoval, jak to funguje. To bylo OK, ale tahal ze mě pořád nějakej obecnej princip, jak to funguje. V rámci toho jsem ještě za pochodu vymýšlel algoritmus na batoh (to se mi vůbec nedělalo dobře, když vedle mě seděl a čekal na výsledek). Na konec jsme se teda asi dobrali toho, co chtěl slyšet - že se řešení konstruuje z menších podúloh stylem zdola nahoru (narozdíl od rozděl&panuj, kde to je v zásadě shora dolů).
  • Dynamicke programovani (Dvorak) - idea, srovnani s rozdel a panuj, priklady (efektivni) a jejich casova slozitost, prejiti do souvisejicich oblasti - popsal sem floyd-washall a batoh od nej jsme presli pres pseudopolynomialni alg, aproximacni batoh (schema) k UPAS, ale byla to volna diskuse ale nevadilo to.
  • Mel jsem srovnat s metodou Rozdel a panuj + ukazat nejaky priklad
  • Motivaci a základní princip dynamického programování. Ukázáno na algoritmech výpočtu Fibonacciho čísel, batohu a Floyd-Warshalova algoritmu. U posledního jmenovaného ze mě zkoušející dostával formální důkaz proč požadujeme nezáporné hrany.
  • Dvořák - Hladové algoritmy - Popsal jsem intuitivně o co jde (oiptimalizační hladové algoritmy), popsal jsem, jak to funguje a popsal jsem Krustalův hladový algoritmus. Bavili jsme se o jeho složitosti (kde jsem neznal způsob, jak to je "ideální"), potom o jeho korektnosti (to jsem taky detaily neznal - nikdy jsem to úplně 100% nepochopil a když jsem se na to koukal do Kapitol z diskrétní matematiky před šesti týdny znova, tak jsem to také úplně nepochopil). Nicméně mi se mě pan Dvořák snažil trochu popostrčit, ale kde nic není, ani smrt nebere. Ukončili jsme to s tím, že to hlavní jsem věděl a že to není fatální.


prakticky otázka z bakaláře, očekává se nějaké naroubování na to co jsme se naučili na NMgr

ROZDILY oproti metode Rozdel a panuj (jsou to dve ruzne metody tvorby algoritmu)

Divide and conquer:

  • Does more work on the sub-problems and hence has more time consumption.
  • In divide and conquer the sub-problems are independent of each other.

Dynamic programming:

Hladový algoritmus[editovat | editovat zdroj]

Amortizovaná složitost[editovat | editovat zdroj]


Průnik se státnicovými otázkami[editovat | editovat zdroj]

Vyčíslitelnost:

Algoritmicky vyčíslitelné funkce, jejich vlastnosti, ekvivalence jejich různých matematických definic. Částečně rekurzivní funkce.

  • PRF, ORF, ČRF (definice)
  • Jejich základní vlastnosti
  • ČRF ⇔ TS
  • Kleenova věta
  • s-m-n?

Rekurzivní a rekurzivně spočetné množiny a jejich vlastnosti.

  • definice RM a RSM
  • vlastnosti
    • (Ne)uzavřenost na sjednocení, průnik a doplněk.
    • Postova věta v kontextu množin.
    • Existenční kvantifikátor a výběrová funkce.
    • generování, rostoucí, def.obor

Algoritmicky nerozhodnutelné problémy (halting problem).

  • definice TS, UTS
  • definice halting problému
  • Věta: Halting problém není algoritmicky rozhodnutelný. (+ důkaz)
  • převoditelnost, Riceova věta

Věty o rekurzi a jejich aplikace, Riceova věta.

  • Věta o rekurzi a její jednoduché důsledky
  • Riceova věta - důkaz pomocí věty o rekurzi.

Složitost:

Metody tvorby algoritmů: rozděl a panuj, dynamické programování, hladový algoritmus.

  • definice rozděl a panuj, dynamické programování a rozdíl mezi nimi
    • příklady
  • definice hladového algoritmu + příklad

Amortizovaná složitost.

  • Asymptotická složitost - definice
  • Amortizovaná složitost - definice

Úplné problémy pro třídu NP, Cook-Levinova věta.

  • definice: třídy NP, polynom.převoditelnost, NP-těžký, NP-úplný
  • zmínit P =? NP
  • Cook-Levinova věta + důkaz

Pseudopolynomiální algoritmy, silná NP-úplnost.

  • Pseudopolynomiální algoritmy definice + příklad
  • silná NP-úplnost definice + příklad (a souvisloti)

Aproximační algoritmy a schémata.

  • definice Aproximační algoritmy a schémata a jejich souvislost s pseudopolynom. algoritmy
  • příklad schémata pro batoh nebo soucet podmnozin

Ostatní[editovat | editovat zdroj]

Npc-small.png