{{Sources|1= úvod: https://www.youtube.com/watch?v=YX40hbAHx3s}}
||
|----|
||
|
* 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ů.|
# Úplné problémy pro trídu NP (9×🎓) #
{{zkazky|1=
* **Np-úplnost (2014, konzultace)** - definice: třídy NP, polynom.převoditelnost, NP-těžký, NP-úplný, zmínit P =? NP, Cook-Levinova věta + důkaz
* **NP-úplné problémy (2014)** - 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.
* **Cook-Levinova veta (2012, 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 :)
* **NP-Uplne problemy (2012)** - 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.
* **Úplné problémy pro třídu NP, Cook-Levinova věta (2012, Čepek/Koubek/Dvořák)** - Č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ě.
* **NP, NP-úplnost, příklady (2012, Král)** - 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ý.
* **NP-uplnost, Cook-Levinova veta (2011, Kucera)** - definice NP, prevoditelnost, NPC, prevod na kachlikovani a na SAT
* **NP-uplnost (2011, Loebl)** - 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.
* **Úplné problémy pro třídu NP + Cook Levinova věta. (2010, Hladík)** - 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-úplnost (2009, Matoušek)** - 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.
}}
{{multiple image
|align = tright
|direction = horizontal
| image1 = Redukce.jpg
| width1 = 331
| caption1 = Ilustrace **polynomiálního převodu/redukce** z jazyka *B* na jazyk *A* pomocí redukční fce *f*. Pro vstup *x* ∈ {0,1}* má otázka zda *x* ∈ *B* stejnou odpověď jako otázka zda *x* ∈ *A*. 💡 myslím že je vidět proč se mu říká někdy redukce(btw *f* NENÍ prostá)
| image2 = Nphard.png
| width2 = 223
| caption2 = **NP-těžkost** ⇐ ∀ jazyk ***B*** ∈ NP: ***B***$≤^p_m$***A***
}}
* odpověď typu ano/ne - **rozhodovací problém** (jestli vstup patří do binární relace *L* ⊆ {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* ⊆ {0, 1}* × {0, 1}* )
### Definice třídy NP ###
**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
**Třída polynomiálně ověřitelných problémů** $NP$ (nedeterministicky polynomiální)
Problém *A* je ve třídě NP, právě když existuje polynomiální NTS *M*, který řeší *A*.
:💡 Na rozdíl od deterministického případu netrváme na tom, že výpočet musí skončit i pro nepřijímané instance.
:💡 **NTS** $M=(Q, \Sigma, \delta, q_0, F)$, kde $\delta:Q\times\Sigma\mapsto\cal P(Q\times\Sigma\times\{R, N, L\})$.
* obdobně jako DTS, ale místo přechodové funkce je zde zobrazení do množiny možných pokračování
alternativní def. pomocí **certifikátů**
::
*L* ∈ NP ⇐ ∃ polynomiální algoritmus (daný jazykem *B*), že polynomiálně dlouhý certifikát *y *dosvědčuje fakt *x* ∈ *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 polynomiálně nepotřebujeme certifikát
### Polynomiální převoditelnost, úplnost a jejich vlastnosti. ###
*B *$≤^p_m$*A* (jazyk *B* **polynomiálně převoditelný/redukovatelný** na *A *) pokud **∃** f: {0,1}*→{0, 1}* spočitatelná v polynomiálním čase a platí: *x* ∈ *B* ⇔ f(*x*) ∈ *A*
Jazyk *A* ∈ **NP-hard** (NP-těžký) ⇐ ∀ jazyk *B* ∈ *NP *: *B *$≤^p_m$*A*
Jazyk *A* ∈ **NPC** (NP-Complete, NP-úplný) ⇐ *A* ∈ *NP* ∧ *A* ∈ NP-hard
## Cook-Levin - KACHL ∈ NPC ##
*
*
::
::
*
*
*
*
*
1.
1.
1.
1.
1.
# Pseudopolynomiální algoritmy, silná NP-úplnost (6×🎓) #
||
|----|
||
|
|
*
*
*
*
*
*
*
*
*
::
::
::
*
*
*
*
*
::
::
::
||
|----|
||
|
|
## Pseudopolynomiální alg. pro (slabě NP-úplný) problém ∃součtu podmnožiny ##
::
*
*
*
::
::
*
::
*
*
*