IB107 Vyčíslitelnost a složitost
třída P, algoritmus C-Y-K, třída NP
Jan Strejček
Fakulta informatiky Masarykova univerzita
opakování
P = {L I Ľ\e rozhodovaný nějakým deterministickým jednopáskovým (nebo vícepáskovým) TM M s časovou složitostí TM{rí) e 0(nk) pro k e N}.
NP = {L | L je rozhodovaný nějakým nedeterministickým jednopáskovým (nebo vícepáskovým) TM M s časovou složitostí TM(ri) e 0(nk) pro k e N}.
■ z definic plyne P c NP
■ otevřený problém P = N P
IB107 Vyčíslitelnost a složitost: třída P, algoritmus C-Y-K, třída NP
2/19
příslušnost problémů v P
■ stačí ukázat, že problém je řešitelný v polynomiálním počtu kroků a že každý krok je proveditelný v polynomiálním čase
■ kódování/dekódování objektů O do/ze slov (O) musí být proveditelné v polynomiálním čase
■ příklad vhodného kódování: reprezentace grafu maticí sousednosti
■ příklad nevhodného kódování: reprezentace sekvence číslic unárním zápisem čísla
IB107 Vyčíslitelnost a složitost: třída P, algoritmus C-Y-K, třída NP
3/19
problém existence cesty
Definice (problém existence cesty)
Problém existence cesty je problém rozhodnout, zda v daném orientovaném grafu G existuje cesta z s do t.
PATH = {(G, s, t) | G je orientovaný graf obsahující cestu z s do
Věta 1.10
PATH g P.
Důkaz: Postupně spočítáme uzly dosažitelné z s. Q označ uzel s
B dokud lze označit nový uzel opakuj: projdi všechny hrany v G
a označ každý uzel, do kterého vede hrana z označeného uzlu Q je-li t označeno, akceptuj; jinak zamítni
Celkem O(n) kroků (n je počet uzlů v G), každý lze provést v polynomiálním čase.
IB107 Vyčíslitelnost a složitost: třída P, algoritmus C-Y-K, třída NP
uzáverové vlastnosti P
Věta
Třída P je uzavřená na sjednocení, průnik, komplement a zřetězení
Důkaz: Nechí L1, L2 e P. Předpokládáme, že L, je rozhodován jednopáskovým det. TM M\ s časovou složitostí v TMi(n) e 0(nki).
IB107 Vyčíslitelnost a složitost: třída P, algoritmus C-Y-K, třída NP
5/19
bezkontextové jazyky a třída P
Věta 1.12
Pro každý bezkontextový jazyk L platí L e P. Důkaz:
■ každý bezkontexotvý jazyk [cr lze popsat gramatikou v Chomského normální formě (CNF)
■ pro pevně danou gramatiku G v CNF a pro slovo i^gF lze v čase 0(|w|3) pomocí algoritmu Cocke-Younger-Kasami rozhodnout, zda w e L(G)
IB107 Vyčíslitelnost a složitost: třída P, algoritmus C-Y-K, třída NP
intuice k algoritmu C-Y-K
S ->• AB | CD | EF Platí S ^* iv ?
IB107 Vyčíslitelnost a složitost: třída P, algoritmus C-Y-K, třída NP
7/19
intuice k algoritmu C-Y-K
Pro každé neprázdné podslovo u slova w spočítáme množinu
Tu všech neterminálů, z kterých lze odvodit u.
■ u = a
■ u = ab
■ u = aĎc
IB107 Vyčíslitelnost a složitost: třída P, algoritmus C-Y-K, třída NP
8/19
příklad
S -> AB | SS | a Platí S ^* abaa ?
>A     AA | SC | a B ^ AB \ b C ^ SA \ b
IB107 Vyčíslitelnost a složitost: třída P, algoritmus C-Y-K, třída NP
9/19
příklad
S      AB | SS A ^ AA \ BC B ^ AB \ b C ^ SA \ b
a a
T,j= {X € /V | X w = abaa
1
1
3 2 1
3 2 1
IB107 Vyčíslitelnost a složitost: třída P, algoritmus C-Y-K, třída NP
10/19
algoritmus Cocke-Younger-Kasami
Vstup: gramatika Q = {N, Z, P, S) v CNF, slovo \n =w^...wn + s Výstup: množiny T,j = {X e N \ X     w-,... }
for / <r-1 to n do
7},i <- 0
for každé pravidlo tvaru (A ->• a) e P do if a = w, then 7},i f- 7},i u {Ä}
od
for /    2 to n do
for / ^- 1 to n - y + 1 do
Ti j <- 0
for /c <r-1 to / - 1 do
for každé pravidlo tvaru (A    SC) e P do
)ÍBeTitk A C e 7}+fci/_fc then Tid <- Tid U {4}
od
od
od
IB107 Vyčíslitelnost a složitost: třída P, algoritmus C-Y-K, třída NP 11/19
problém hamiltonovské cesty
hamiltonovská cesta = cesta procházející každým uzlem právě jednou
Definice (problém hamiltonovské cesty)
Problém hamiltonovské cesty je problém rozhodnout, zda v daném orientovaném grafu G existuje hamiltonovská cesta z s do t.
HAMPATH = {(G, s, t) \G je orientovaný graf obsahující
hamiltonovskou cestu z s do t}
IB107 Vyčíslitelnost a složitost: třída P, algoritmus C-Y-K, třída NP
12/19
problém hamiltonovské cesty
Věta
HAMPATH g A/P.
Důkaz:
■ hamiltonovská cesta v grafu G s n uzly má délku n - 1
■ hamiltonovskou cestu budeme nedeterministicky hádat
O začni budovat cestu z uzlu s
H (a? - 1 )-krát opakuj: nedeterministicky vyber hranu vedoucí z posledního uzlu cesty a přidej ji na konec cesty
B je-li t poslední uzel cesty a žádný uzel se neopakuje, akceptuj; jinak zamítni
■ každý výpočet má O (n) polynomiálních kroků
■ hamiltonovská cesta existuje <=^> existuje akceptující výpočet
IB107 Vyčíslitelnost a složitost: třída P, algoritmus C-Y-K, třída NP
13/19
problém složených čísel
Definice (problém složených čísel)
Problém složených čísel je problém rozhodnout, zda je dané číslo x složené, tedy součinem dvou čísel větších než 1.
COMPOSITES = {(x) I x = pq pro nějaká přirozená čísla p,q> 1}
Věta
COMPOSITES e NP.
Důkaz: Nedeterministicky zvolíme číslo p takové, že 1 < p < x. Pokud p je dělitelem x, akceptujeme, jinak zamítneme. ■
V roce 2002 bylo dokázáno, že COMPOSITES e P.
IB107 Vyčíslitelnost a složitost: třída P, algoritmus C-Y-K, třída NP
14/19
problém splnitelnosti (SAT)
Definice (problém splnitelnosti (SAT))
Problém splnitelnosti (SAT) je problém rozhodnout, zda je daná výroková formule (využívajícípouze operace A, v a -n) splnitelná.
SAT = {((p) | (fje splnitelná výroková formule}
SAT g N P.
Důkaz:
IB107 Vyčíslitelnost a složitost: třída P, algoritmus C-Y-K, třída NP
15/19
polynomiální verifikátor
"Řešení" problému lze deterministickým TM v polynomiální čase
■ nalézt, pokud je problém v P
■ ověřit, pokud je problém v NP (když nám řešení někdo dodá)
Definice (polynomiální verifikátor)
Polynomiální verifikátor pro jazyk L je deterministický TM V splňující
w g L <=^> existuje řetězec c takový, že V akceptuje (w, c
a pracující v polynomiálním case vzhledem k | w
c se nazývá svědek, důkaz nebo certifikát příslušnosti w do L
lze předpokládat, že velikost c je polynomilální vzhledem k \ w\, protože polynomiální verifikátor více znaků z c nemůže přečíst
IB107 Vyčíslitelnost a složitost: třída P, algoritmus C-Y-K, třída NP
16/19
polynomiální verifikátory a NP
Věta
L g NP <=^> existuje polynomiální verifikátor pro L. Důkaz:
=4> Nechí M je nedeterministický TM akceptující L
v polynomiálním čase. Verifikátor bude pro vstup (w, c) simulovat M na vstupu w ac bude používat k deterministickému výběru z možných přechodů.
<== Nechí V je polynomiální verifikátor pro L pracující na vstupech (i/i/, c) v čase 0(1^1^). Nedeterministický stroj M nedeterministicky zvolí řetězec c délky nejvýše \ w\k a pak simuluje V na vstupu (w, c). ■
IB107 Vyčíslitelnost a složitost: třída P, algoritmus C-Y-K, třída NP
17/19
uzáverové vlastnosti N P
Věta
Třída NP je uzavřená na sjednocení, průnik a zřetězení Důkaz:
■ sjednocení a průnik: analogicky jako pro P
■ zřetězení:
IB107 Vyčíslitelnost a složitost: třída P, algoritmus C-Y-K, třída NP
uzavřenost NP na doplněk
■ není známo, zda je třída NP uzavřená na doplněk
■ například nevíme, zda HAMPATH e NP,
■ tedy nevíme, jak polynomiálně verifikovat HAMPATH
■ lze definovat třídu
coNP = {/_|Ie NP}
■ věří se, že platí NP ^ coNP, tj. NP není uzavřená na doplněk
■ z NP ^ coNP plyne P ^ NP
■ existují problémy, které jsou v NP n coNP, ale není známo, zda jsou v P, například problém paritních her
IB107 Vyčíslitelnost a složitost: třída P, algoritmus C-Y-K, třída NP
19/19