(k-páskový deterministický) TS je 5-tice: M = (Q, ∑, δ, q₀, F)
* Q je konečná množina stavů (řídící jednotky) * ∑ je konečná pásková abeceda ** obsahuje znak λ pro prázdné políčko * <math>δ : Q \times ∑^k -> Q \times ∑^k \times \{R, N, L\}^k ∪ \{⊥\}</math> je přechodová fce ** ⊥ je nedefinovaný přechod * q₀ ∈ 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<math>≤^p_m</math><font color=red>A</font>

}}

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í:

<math> P= \bigcup_{i\in \mathbb N}DTIME(n^i)</math> - problémy rozhodnutelné v polynomiálním čase
<math> PSPACE=\bigcup_{i\in\mathbb N}DSPACE(n^i)</math> - problémy rozhodnutelné v polynomiálním prostoru

Třída polynomiálně ověřitelných problémů <math>NP</math> (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 <math>M=(Q, \Sigma, \delta, q_0, F)</math>, kde <math>\delta:Q\times\Sigma\mapsto\cal P(Q\times\Sigma\times\{R, N, L\})</math>.

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 <math>≤^p_m</math>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 <math>≤^p_m</math>A

Jazyk A ∈ NPC (NP-Complete, NP-úplný) ⇐ A ∈ NP ∧ A ∈ NP-hard

Cook-Levin - KACHL ∈ NPC

Pseudopolynomiální algoritmy, silná NP-úplnost (6×🎓)

omezení max čísla v instanci polynomem její délky

buď prvek přidám nebo ne

Pseudopolynomiální alg. pro (slabě NP-úplný) problém ∃součtu podmnožiny