SLOITOST PRO KRYPTOGRAFII T
PÁN HOLUB
Obsah 1.
Algoritmy a problémy
1
2.
Turingovy stroje
3
3.
Rekursivní funkce a jazyky
5
4.
Nedeterministické stroje
9
5.
Sloºitostní t°ídy
10
6.
Realisti£t¥j²í výpo£etní modely
12
6.1.
Vícepáskové Turingovy stroje
12
6.2.
Stroje RAM
13
7.
Vztahy mezi t°ídami
16
8.
Booleovské formule a obvody
21
9.
Redukce a úplnost
24
10.
Alternativní charakteristika t°ídy NP
25
11.
NP-úplnost
26
12.
Pravd¥podobnostní odhady
31
13.
Pravd¥podobnostní algoritmy a sloºitostní t°ídy
34
14.
Neuniformní sloºitost
37
15.
Rozli²itelnost náhodných distribucí
39
16.
Jednosm¥rné funkce a t¥ºký bit
42
17.
Pseudonáhodné generátory
45
18.
D·kazové systémy
47
1. Algoritmy a problémy V matematice se £asto setkáváme s tvrzeními týkajícími se objekt·, které neumíme zkonstruovat. M·ºeme nap°. de novat mnoºinu, na které dva homomor smy (nap°. volné pologrupy) nabývají stejných hodnot, nebo mnoºinu posloupností generujících prvk· grupy, jejichº sou£in je roven jedné. Zájem o konstruktivní stránku matematiky byl v moderní matematice spí²e okrajový. Rozvoj výpo£etní techniky, který poskytl matematice d°íve netu²ené moºnosti, zájem o problematiku konstruktivního p°ístupu výrazn¥ posílil. Moºnosti poskytnuté po£íta£em obrátily pozornost k hranicím t¥chto moºností. Navzdory naivnímu p°edpokladu, ºe hranice moºností výpo£etní techniky spo£ívají pouze v technické stránce v¥ci, se objevila celá v¥dní disciplína týkající se samotné
moºnosti
n¥jaký problém algoritmicky vy°e²it. Uká-
zalo se totiº, ºe n¥které jednodu²e formulované problémy takové algoritmické °e²ení nemají, a to nikoli z d·vodu nedostate£ného d·vtipu programátor· nebo technické nedokonalosti hardwaru, nýbrº z hlubokých a podstatných teoretických d·vod·. Z°ejm¥ nejslavn¥j²ím p°íkladem takové
nerozhodnutelné úlohy je tzv. Hilbert·v de-
sátý problém, který byl sou£ástí seznamu p°edloºeného slavným n¥meckým matematikem Davidem Hilbertem v roce 1900 jako výzva pro matematiku 20. století: ZS 2014/2015.
1
2
T
PÁN HOLUB 10.
Ur£ení °e²itelnosti diofantické rovnice. J e dána diofantická rov-
nice s libovolným po£tem neznámých a racionálními £íselnými koe cienty: je t°eba sestavit postup, kterým je moºno kone£ným po£tem krok· ur£it, zda je rovnice °e²itelná v oboru celých £ísel.
Entscheidung der Lösbarkeit einer diophantischen Gleichung. Eine diophantische Gleichung mit irgendwelchen Unbekann(10.
ten und mit ganzen rationalen Zahlkoe cienten sei vorgelegt:
man
soll ein Verfahren angeben, nach welchen sich mittels einer endlichen Anzahl von Operationen entscheiden lässt, ob die Gleichung in ganzen rationalen Zahlen lösbar ist.)
Negativní °e²ení tohoto problému, tedy d·kaz, ºe takový postup neexistuje, podal v roce 1970 Jurij Matijasevi£. Tvrzení, ºe neexistuje postup, který by v kone£ném po£tu krok· vy°e²il n¥jaký problém, vyºaduje up°esn¥ní. Takovým postupem by totiº mohla být nap°. soust°ed¥ná snaha v²ech ºijících matematik· o dané rovnici rozhodnout, zda je, nebo není °e²itelná. Není jasné, jak by bylo v·bec moºné dokázat, ºe takový postup nevede v kone£ném £ase k cíli. Od postupu, poºadovaného Hilbertem, o£ekáváme intuitivn¥ n¥kolik vlastností:
• Uniformita. S kaºdým p°ípadem se zachází stejn¥. • Jednozna£nost. V kaºdé fázi postupu musí být z°ejmé, jak pokra£ovat. (P°ípadn¥ musí existovat kone£n¥ mnoho pokra£ování, mezi nimiº se p°edepsaným postupem, nap°. hodem mincí, vybírá.)
• Mechani£nost.
Postup nesmí vyºadovat ºádný d·vtip. Musí být realizo-
vatelný mechanickým za°ízením, strojem, resp. d·kladným ú°edníkem bez vlastního názoru. V pr·b¥hu dvacátého století bylo navrºeno n¥kolik model· popisujících, jak má takový postup vypadat. Budeme je nazývat
výpo£etní modely. Nejslavn¥j²í a nejd·-
leºit¥j²í výpo£etní model navrhl Alan Turing ve svém £lánku z roku 1936 On computable numbers with an application to the Entscheidungsproblem, Proc. London Math. Soc. 42 (1936) 230265. Po svém tv·rci se nazývá Turing·v stroj (Turing machine) a budeme se jím podrobn¥ zabývat. Zmín¥ný £lánek je pozoruhodný tím, ºe obsahuje nejen geniální intuice, ale také detailní rozpracování problému aº k popisu tzv. univerzálního stroje, coº je vlastn¥ první opera£ní systém . Turing také d·kladn¥ vysv¥tluje, pro£ se domnívá, ºe jím navrºený výpo£etní model zahrnuje v²echny postupy, které je moºno rozumn¥ povaºovat za algoritmus ve vý²e uvedeném smyslu. Toto p°esv¥d£ení se proslavilo pod názvem Churchova, resp. Churchova-Turingova teze:
Churchova-Turingova teze: Kaºdý výpo£etní postup lze realizovat Turingovým strojem. Churchova teze není matematické tvrzení, protoºe pojem výpo£etního postupu je zaloºen pouze na intuici. Soust°ed¥ný zájem v²ech matematik· nap°. za výpo£etní postup nepovaºujeme, protoºe nespl¬uje (p°inejmen²ím) podmínku mechani£nosti. Kde je ale p°esná hranice výpo£etních postup· není apriori jasné. P°esto je tato teze v²eobecn¥ p°ijímána, protoºe argumenty uvád¥né Turingem v její prosp¥ch jsou velmi p°esv¥d£ivé a navíc ji potvrzuje intenzivní výzkum v pr·b¥hu celého dvacátého století, kdy se ukázalo, ºe v²echny alternativní výpo£etní modely jsou s Turingovým strojem ekvivalentní (nebo slab²í). V²eobecný souhlas s Churchovou tezí vede k tomu, ºe bývá obracena a pouºívána jako
de nice
výpo£etního postupu:
SLOITOST PRO KRYPTOGRAFII
De nice 1.1
(Obrácená Churchova teze)
.
3
Výpo£etním postupem (algoritmem)
je
to a jen to, co lze realizovat Turingovým strojem. Prot¥j²kem algoritmu je
P°íklad
1.2.
algoritmický problém.
Uve¤me n¥kolik p°íklad·:
(1) Pro dané p°irozené £íslo najdi n¥jaký jeho faktor.
(2) Zjisti, zda dané p°irozené £íslo je prvo£íslo. (3) Zjisti, zda daná diofantická rovnice má °e²ení. (4) Najdi nejkrat²í cestu mezi dv¥ma body orientovaného grafu. (5) Zjisti, zda v daném grafu existuje hamiltonovská cesta. Algoritmický problém se li²í od oby£ejného problému v tom, ºe nehledáme odpov¥¤ pro jednotlivý p°ípad (nap°. jednotlivý graf ), ale algoritmus, který najde odpov¥¤ pro v²echny moºné vstupy. Algoritmický problém je tedy mnoºina
stancí,
in-
tedy v²ech moºných zadání problému. Tato mnoºina je typicky nekone£ná.
Problémy s kone£n¥ mnoha instancemi nejsou z teoretického hlediska zajímavé, protoºe vºdy existuje algoritmus, který spo£ívá v tabulce správných odpov¥dí. (Existují samoz°ejm¥ i problémy s kone£n¥ mnoha instancemi, které jsou z praktického hlediska zajímavé, nap°. problém rozhodnout v dané pozici na ²achovnici, zda existuje vít¥zný tah.) Na druhou stranu, kaºdá instance problému musí být kone£ná, aby mohla být zadána. Problém je tedy typicky
spo£etná mnoºina instancí. vyhledávací a rozhodovací.
Podle typu odpov¥di rozeznáváme problémy
U roz-
hodovacího problému o£ekáváme odpov¥¤ ANO/NE (jsou to nap°. vý²e uvedené problémy 2, 3 a 5), vyhledávací problém má v¥t²í mnoºinu moºných odpov¥dí, typicky op¥t spo£etn¥ nekone£nou (nap°. problémy 1 a 4). Z praktických d·vod· £asto omezíme na²e zkoumání na problémy rozhodovací. Toto omezení není tak zásadní, jak by mohlo vypadat. Vyhledávací problémy lze p°evést na sérii rozhodovacích problém· typu: je
i-tý
bit odpov¥di
0
nebo
1? .
Pokud je nap°. takový rozhodovací problém polynomiální, je také výsledný vyhledávací algoritmus polynomiální. 2. Turingovy stroje Stroj, který jako univerzální výpo£etní model navrhl Turing, má podobu na ob¥ strany nekone£né pásky rozd¥lené na polí£ka a opat°ené okamºiku nachází na jednom polí£ku pásky. Polí£ka mohou být prázdná nebo nést r·zné
symboly
hlavou,
která se v daném
vybrané z n¥jaké kone£né
mnoºiny. Hlava m·ºe £íst a p°episovat symbol na polí£ku, na kterém se nachází, a pohybovat se po pásce vpravo nebo vlevo. Krom¥ toho obsahuje vnit°ní pam¥´, která m·ºe nabývat kone£ného po£tu
stav·.
Na po£átku výpo£tu je páska prázdná aº na kone£nou souvislou posloupnost polí£ek, která nese
vstup.
Hlava je na prvním polí£ku vstupu.
Chování stroje se °ídí programem, coº je mnoºina instrukcí p°edepisujících, co má hlava v daném okamºiku v závislosti na svém stavu a £teném symbolu d¥lat. Algoritmus je skryt práv¥ v programu, z matematického hlediska je Turing·v stroj totoºný se svým programem. Matematicky tedy de nujeme Turing·v stroj následovn¥.
De nice 2.1
.
Nech´ Σ a Q jsou neprázdné kone£né mnoºiny. symbol·, mnoºinu Q mnoºinou stav·. Mnoºina Σ obsahuje symbol , který znamená prázdné polí£ko. Mnoºina Q obsahuje jeden význa£ný prvek qs , který nazýváme po£áte£ní stav. Nech´ M = {←, →, −}. Program Turingova stroje je libovolná podmnoºina P ⊆ Q × Σ × Q × Σ × M. 0 0 Libovolný prvek (q, s, q , s , m) ∈ P se nazývá instrukce. Turing·v stroj je £tve°ice T = (Q, Σ, qs , P ).
Mnoºinu
Σ
(Turing·v stroj)
nazveme mnoºinou
4
T
PÁN HOLUB Mnoºinu v²ech Turingových stroj· zna£íme
TM.
Mnoºinu kone£ných posloupností symbol· z mnoºiny nosti) zna£íme
Σ∗ .
Σ (v£etn¥ prázdné posloup-
Takové posloupnosti pí²eme typicky bez £árek a nazýváme je
slova, p°i£emº prvky Σ nazýváme písmena. Mnoºinu neprázdných slov zna£íme Σ+ . ∗ Turing·v stroj T spolu se svým vstupem x ∈ Σ de nuje výpo£et. Na po£átku vý-
po£tu je hlava umíst¥na na prvním symbolu vstupu. Výpo£et sestává z jednotlivých
krok·.
mentální stav hlavy a
£tený symbol.
tzv.
s
je symbol na polí£ku, na kterém se hlava práv¥ nachází,
Následující krok je dán instrukcí
• • •
okamºitým popisem (q, s) ∈ Q × Σ, kde q je mo-
Kaºdý krok spo£ívá v aplikaci jedné instrukce a je dán
stroje v daném okamºiku. Okamºitý popis je dvojice
£tený symbol se zm¥ní z stav hlavy se zm¥ní z hlava provede pohyb
Moºné pohyby hlavy jsou t°i. na sousední pravé polí£ko a
s
(q, s, q 0 , s0 , m) ∈ P
na
q an q m.
0
a má t°i sloºky:
s0 ,
,
← znamená pohyb na sousední levé polí£ko, → pohyb − znamená, ºe hlava z·stane na stejném polí£ku, na
kterém byla na za£átku kroku. Výpo£et skon£í, pokud se stroj dostane do okamºitého popisu, pro který neexistuje ºádná instrukce (coº typicky znamená, ºe dosáhl Po ukon£ení výpo£tu z·stane na pásce
výstup,
koncového
stavu).
coº je posloupnost neprázdných
symbol·, které se na pásce vyskytují. Pokud výpo£et neskon£í, °ekneme, ºe výpo£et stroje Jinak °íkáme, ºe
konverguje.
T
na vstupu
x diverguje.
Na Turingovy stroje se £asto kladou dodate£né poºadavky, které usnad¬ují jejich studium. Takové dodate£né poºadavky budeme vzná²et, kdykoli to bude vhodné. Vºdy by m¥lo být z°ejmé, ºe nemají vliv na zkoumané vlastnosti. K nej£ast¥j²ím poºadavk·m pat°í:
•
Výpo£et, pokud konverguje, kon£í vºdy v jednom koncovém stavu, který se jinak b¥hem výpo£tu nepouºívá.
•
Stroj nikdy nezapisuje prázdný symbol. V tomto p°ípad¥ se obvykle zavádí nový pseudoprázdný symbol, který odli²í prázdné nenav²tívené polí£ko od prázdného nav²tíveného a který není povaºován za sou£ást výstupu.
• •
Výstup je souvislý, není p°eru²en prázdnými ani pseudoprázdnými symboly. Hlava nikdy nez·stává na míst¥. Mnoºina
M
se tedy omezuje na
{←, →}
Na²e de nice Turingova stroje nevyºaduje, aby pro daný okamºitý popis existovala jediná instrukce. Pokud existuje instrukcí více, není výpo£et de nován jedno-
nedeterministické. TM.
zna£n¥. Turingovy stroje jsou tedy obecn¥ skute£nost zd·raznit, pí²eme Pokud má stroj
terministický.
T
NTM
místo
Pokud chceme tuto
deDTM.
pro kaºdý okamºitý popis jedinou instrukci, nazývá se
Mnoºinu deterministických Turingových stroj· ozna£ujeme
Deterministický stroj chápeme jako zvlá²tní p°ípad stroje nedeterministického, je tedy
DTM ( NTM.
Okamºitý popis Turingova stroje je lokální, omezuje se na situaci v míst¥ hlavy. Celkový stav pásky v daném okamºiku nazýváme
úplný popis
nebo
snímek
stroje.
Snímek zapisujeme
σ = ω u1 q u2 , ω , kde
u1 u2
je úsek pásky obsahující neprázdné symboly. Pokud p°ijmeme konvenci,
u1 u2 ∈ (Σ \ {})∗ . Hlava £te ω koncové m·ºeme vynechávat.
ºe stroj nezapisuje prázdné symboly, je z
u2
a je ve stavu
q.
Po£áte£ní a
první symbol
SLOITOST PRO KRYPTOGRAFII Po£áte£ní snímek stroje se vstupem relaci
δT
x
5
q s x.
je tedy
Turing·v stroj
T
de nuje
mezi snímky. Pí²eme
δ
T σ2 , σ1 −→
pokud snímek
P°íklad
σ2
vznikne ze snímku
2.2. Instrukce
(q, 1, q 0 , 0, →)
Tranzitivní obal relace
δT
σ1
jedním krokem.
p°evádí snímek
zna£íme
δT∗ .
10q10
na
100q 0 0.
Zápis
∗ δT
σ1 −→ σ2 , tedy znamená, ºe existuje (libovoln¥ dlouhý) výpo£et, který p°evádí snímek snímek
σ1
na
σ2 .
V p°ípad¥ deterministického Turingova stroje existuje pro kaºdý vstup nejvý²e jeden výstup nebo stroj diverguje. Pro
x jako T (x), T (x) =%.
T ∈ DTM
ozna£ujeme výstup
p°i£emº pro divergující výpo£et de nujeme nový symbol
T na %a
vstupu pí²eme
Skute£nost, ºe Turing·v stroj je totoºný se svým programem m·ºe být matoucí. O£ekáváme, ºe stroj se bude podobat spí²e po£íta£i, který programy vykonává. Po£íta£ je ov²em také program, a sice opera£ní systém, který umí v²echny ostatní programy realizovat. Tomu odpovídá pojem
Tvrzení 2.3. platí
univerzálního Turingova stroje.
Existuje Turing·v stroj U ∈ DTM takový, ºe pro kaºdý T ∈ DTM U ([T ], x) = T (x),
kde [T ] je n¥jaký vhodný kód stroje T . Práce univerzálního stroje
U
je zaloºena na simulaci práce stroje
T,
který je
na vstupu reprezentován n¥jakým svým kódem , nejtypi£t¥ji n¥jakým zápisem svých instrukcí. My²lenka, ºe v²echny moºné algoritmy je moºné realizovat jediným strojem pomocí programu, který je uloºen v pam¥ti podobn¥ jako vstup (tzv.
stored-program computer ),
je zásadním p°ínosem Alana Turinga a znamenala fak-
tický za£átek teoretické informatiky. Poznamenejme, ºe p·vodní Turing·v £lánek obsahuje detailní popis programu univerzálního stroje. 3. Rekursivní funkce a jazyky Vstupem i výstupem Turingova stroje je n¥jaký prvek
∗
Σ∗ .
Deterministický stroj
∗
Σ → Σ . To je v souladu se zvoleným zápisem T (x) = y , pokud je y výstupem stroje T na vstupu x. Zd·razn¥me, ºe tato de nice dává dobrý smysl pouze pro deterministické stroje. Pokud stroj na vstupu x diverguje, pí²eme T (x) =%, coº je nejlep²í chápat tak, ºe funkce T není na x T
tedy m·ºeme chápat jako zobrazení
de nována.
Σ∗
je spo£etná mnoºina, lze ji tedy o£íslovat p°irozenými £ísly.
n¥jaké mnoºiny mnoºiny
Σ∗
S
rozumíme libovolnou bijekci
f : N → S.
je dáno jeho maximo-lexikogra ckým uspo°ádáním
De nice 3.1 (Maximo-lexikogra cké uspo°ádání).
O£íslováním
Nejvhodn¥j²í o£íslování
≺.
Uvaºujme n¥jaké lineární uspo-
Σ a p°íslu²né lexikogra cké uspo°ádání < na Σ∗ . Maximo-lexikogra cké uspo°ádání ≺ odpovídající < je de nováno a) Je-li u del²í neº v , pak v ≺ u. b) Mají-li u a v stejnou délku, je u ≺ v práv¥ kdyº je u < v .
°ádání prvk·
ϕ : N → Σ∗ . ϕ(0) je prázdný °et¥zec a ϕ(i) je i-té uspo°ádání ≺. P°irozenost tohoto uspo°ádání spo£ívá v tom, ºe
Takto de nujeme bijekci neprázdné slovo v
pravidly:
6
T
PÁN HOLUB
pokud
m,
Σ = {1, 2, . . . , k}
a
<
je b¥ºné uspo°ádání, pak
ϕ(m)
je
k -adický
zápis £ísla
tj.
cj cj−1 . . . c1 = ϕ
j X
! ci · k
j−i
.
i=1
Σ∗ p°irozenými £ísly, odpovídá kaºdý deterministický Turing·v stroj T ∈ DTM £áste£né funkci fT : N → N, která není de nována na vstupech, na kterých T diverguje. Nyní se zam¥°íme na deterministické stroje. Uvaºujeme-li o£íslování
V tomto smyslu kaºdý algoritmus spo£ívá ve výpo£tu n¥jaké funkce: pro danou instanci/vstup/£íslo ur£it odpov¥¤/výstup/obraz.
De nice 3.2 (Rekursivní funkce). n¥jaký
T ∈ DT M
takový, ºe
se nazývá
rekursivní funkce de novaná na celém
rekursivní.
f : N → N, pro kterou existuje £áste£ná rekursivní. Je-li £áste£ná N nazývá se úplná rekursivní nebo prost¥
áste£ná funkce
f = fT ,
Mnoºinu v²ech £áste£ných rekursivních funkcí budeme zna£it sive functions) a mnoºinu rekursivních funkcí
PRF (partial recur-
RF.
ekli jsme, ºe kaºdý deterministický Turing·v stroj p°edstavuje n¥jakou £áste£nou rekursivní funkci. To ov²em neznamená, ºe m·ºeme mnoºiny ztotoºnit.
DTM
DTM
a
PRF
obsahuje v²echny deterministické Turingovy stroje, tedy v²echny
moºné deterministické seznamy instrukcí. Mnoho r·zných Turingových stroj· v²ak po£ítá stejnou funkci. Sta£í uváºit stroj, ke kterému p°idáme stav, který nebude nikdy dosaºen. Pro takový stav pak m·ºeme libovoln¥ tvo°it instrukce, aniº se p°íslu²ná funkce zm¥ní. O objektech, které lze algoritmicky zkonstruovat °íkáme, ºe existují
efektivn¥,
jako v následujícím tvrzení. V n¥m se také poprve setkáváme s klí£ovou my²lenkou teorie rekursivních funkcí: Vzhledem k tomu, ºe Turing·v stroj je dán mnoºinou svých instrukcí, je moºné ho chápat jako n¥jaké slovo, n¥jakou posloupnost znak· z kone£né abecedy. Turingovy stroje sice obecn¥ obsahují neomezen¥ mnoho symbol· a stav·, ale v²echny je lze zakódovat kone£nou abecedou (sta£í binární abeceda, coº se, jak dob°e víme, skute£n¥ d¥je ve výpo£etní technice). Turing·v stroj se tedy m·ºe stát
svým vlastním vstupem,
coº je, jak uvidíme pozd¥ji, velmi d·leºité.
Tvrzení 3.3.
Existuje kódování (deterministických) Turingových stroj·, které lze efektivn¥ o£íslovat. D·kaz.
Σ a uvaºujme v této abeced¥ n¥jaké TM ⊂ Σ+ . M·ºeme zvolit Σ = {0, 1} nebo, pro lep²í p°edstavu, n¥jakou bohat²í abecedu, nap°. Σ = {0, 1, $, (, |, )}. Zvolme n¥jakou xní kone£nou abecedu
kódování mnoºiny
TM
Turingových stroj·. Tedy
Zakódovaný Turing·v stroj pak m·ºe vypadat nap°. takto:
(0|0|1|0|1)$(0|1|0|1|1)$(1|1|1|1|1)$(1|10|10|10|1)$(0|10|10|0|1) ≺. G : N → TM. Hodnota G(i) je kód Turingova stroje, TM vzhledem k maximo-lexikogra ckému uspo°ádání.
Turingovy stroje budeme £íslovat podle maximo-lexikogra ckého uspo°ádání Ozna£me takové o£íslování který je
i-tým
slovem z
Ukaºme, ºe funkce
G je rekursivní. Turing·v stroj, který ji po£ítá, bude postupn¥ Σ+ . U kaºdého
v maximo-lexikogra ckém uspo°ádání generovat v²echna slova ze
slova ov¥°í, zda se jedná o platný kód (deterministického) Turingova stroje, a pokud ano, zvý²í své po£ítadlo (vyhrazený kus pásky) o jedna. Ve chvíli, kdy na po£ítadle dosáhne vstupní hodnotu stroje.
i,
oznámí jako výstup poslední nalezený kód Turingova
My²lenka £íslování mnoºiny kone£ných posloupností pochází od Kurta Gödela, který ji poprve pouºil v kontextu formální logiky pro o£íslování logických formulí.
SLOITOST PRO KRYPTOGRAFII Na jeho po£est pouºíváme zna£ení
G.
7
Takové o£íslování se také n¥kdy nazývá Gö-
delovo. Po p°edchozím positivním výsledku obrátíme svou pozornost k výsledk·m negativním. Optimistická p°edstava, podle které lze kaºdý problém °e²it algoritmicky, je neudrºitelná uº proto, ºe v²ech funkcí je nespo£etn¥ mnoho (kontinuum), zatímco Turingových stroj·, a tedy rekursivních funkcí jen spo£etn¥. M·ºeme tedy dokonce °íci, ºe funkce jsou v drtivé v¥t²in¥ nerekursivní. Problémy, které nás v matematice zajímají, jsou ov²em vºdy formulovány n¥jakým kone£ným popisem. Není tedy p°edem z°ejmé, zda existují n¥jaké nerekursivní p°irozené problémy. Jak jsme uvedli v úvodu, ukazuje se, ºe i velmi konkrétní matematické problémy jsou nerekursivní, neboli
nerozhodnutelné.
V²imn¥te si, ºe terminologie je z historických d·vod· dosti rozr·zn¥ná. Termíny
efektivní, rekursivní, rozhodnutelný
mají v podstat¥ totoºný význam, a£koli se po-
uºívají v r·zných kontextech (efektivní £íslování, rekursivní funkce, rozhodnutelný problém). Historicky nejstar²í a teoreticky nejd·leºit¥j²í nerozhodnutelné problémy se týkají otázky, zda daný stroj na daném vstupu konverguje, coº souvisí s otázkou zda je funkce po£ítaná daným stroj úplná. Ozna£me
UTM
mnoºinu deterministických
stroj·, které po£ítají úplnou funkci.
Tvrzení 3.4.
Neexistuje efektivní o£íslování mnoºiny UTM.
D·kaz. Budeme postupovat sporem. P°edpokládejme, ºe existuje rekursivní funkce G : N → UTM. Uvaºme funkci F : N → N de novanou p°edpisem F (i) := fG(i) (i) + 1. F je rekursivní. Díky rekursivit¥ G lze pro dané i efektivn¥ M = G(i) ∈ UTM, který po£ítá funkci fG(i) , a pomocí tohoto stroje pak spo£ítáme hodnotu F (i) jako výstup M na vstupu i zv¥t²ený o jedna. Funkce F je navíc úplná, a proto existuje stroj T ∈ UTM, který ji po£ítá, a p°irozené £íslo iF , pro které G(iF ) = T . Spor dosáhneme otázkou po hodnot¥ funkce F v bod¥ iF . Podle de nice F platí Ukaºme, ºe funkce
nalézt stroj
F (iF ) = fG(iF ) (iF ) + 1 Av²ak funkce
fG(iF ) je rovna
F,
a tudíº
F (iF ) = F (iF ) + 1,
spor.
Hlavní my²lenka p°edchozího d·kazu se nazývá diagonální argument, protoºe funkce
F
byla de nována jako diagonála tabulky hodnot funkcí
G(i)
jednu. Stejný postup znáte z d·kazu toho, ºe reálná £ísla v intervalu
zv¥t²ená o
[0, 1]
nelze
o£íslovat p°irozenými £ísly. Následující v¥ta je prototyp a zdroj v²ech v¥t o nerozhodnutelnosti.
V¥ta 3.5.
Nelze rozhodnout, zda se Turing·v stroj na daném vstupu zastaví (neboli zda je daná £áste£n¥ rekursivní funkce na dané hodnot¥ de novaná). D·kaz.
Nech´
G je efektivní £íslování DTM, zaru£ené Tvrzením 3.3. Chceme pouºít F podobn¥ jako v p°edchozí v¥t¥. Nyní ov²em G(i)
diagonální argument a funkci m·ºe v bod¥
i
divergovat.
F takto ( fG(i) (i) + 1, F (i) := 0,
De nujme tedy
G(i) na vstupu i zastaví, G(i) na vstupu i diverguje.
pokud se pokud
8
T
PÁN HOLUB Je-li funkce
vodem, pro£
F
F
rekursivní, dostaneme spor jako v p°edchozí v¥t¥. Jediným d·-
není rekursivní m·ºe být neexistence algoritmu, který rozhodne,
kterou ze dvou v¥tví de nice
F
pouºít. Tím je v¥ta dokázána.
P°edchozí v¥ta se £asto formuluje slovy: HaltingProblem je nerozhodnutelný. Zd·razn¥me, ºe nerozhodnutelnost problému neznamená, ºe pro n¥j nelze v konkrétním p°ípad¥ nalézt °e²ení. Znamená neexistenci algoritmu, který bude úsp¥²ný
v²echny
pro
instance.
V p°edchozím textu jsme uvedli do souvislosti algoritmy a funkce
N → N.
V
p°ípad¥ rozhodovacích problém·, tj. takových, u kterých je výstupem odpov¥¤ ANO nebo NE, je situace je²t¥ o n¥co jednodu²²í. Za obor hodnot p°íslu²ných funkcí m·ºeme povaºovat mnoºinu
{0, 1}
a funkce je charakteristickou funkcí mnoºiny
instancí s kladnou odpov¥dí. Algoritmus má pro daný vstup rozhodnout, zda v mnoºin¥ leºí. Vstupem jsou slova ze
Σ∗ ,
libovolná mnoºina slov se nazývá
Vzhledem k existenci efektivního o£íslování ºin¥
N.
kaºdý jazyk podmno-
Máme tedy t°i vzájemn¥ si odpovídající úhly pohledu:
rozhodovací problémy Pro
jazyk. Σ∗ , odpovídá
deterministické
De nice 3.6. práv¥ kdyº
≡
pro
mnoºiny p°irozených £ísel
stroje máme následující de nice.
ekneme, ºe stroj
T ∈ DTM p°ijímá
jazyk
L ⊂ Σ∗ ,
pokud
x ∈ L,
T (x) = 1. T ∈ DTM rozhoduje x ∈ L platí T (x) = 1 a x∈ / L platí T (x) = 0.
ekneme, ºe stroj pro
≡
jazyky
jazyk
L ⊂ Σ∗ ,
pokud
Zásadní rozdíl mezi p°ijímáním a rozhodováním jazyka spo£ívá v tom, ºe p°ijímající stroj m·ºe na vstupu
x∈ /L
divergovat.
Jazyk, který je p°ijímán n¥jakým deterministickým Turingovým strojem se na-
rekursivn¥ spo£etný. Jazyk, který je n¥jakým takovým strojem rozhodován se rekursivní. Mnoºinu rekursivn¥ spo£etných jazyk· zna£íme RE (recursively enumerable) a mnoºinu rekursivních jazyk· R. Komplement jazyka L je jazyk L = Σ∗ \ L. Mnoºinu jazyk·, jejichº komplement je rekursivn¥ spo£etný zna£íme co-RE. zývá
nazývá
Tvrzení 3.7. R = RE
D·kaz.
\
co-RE.
Je-li jazyk rekursivní pak je on i jeho komplement z°ejm¥ rekursivn¥ spo-
£etný.
¯ rekurzivn¥ spo£etné, pak existují Turingovy stroje M1 a M2 LaL . Zkonstruujeme Turing·v stroj T pomocí takové, ºe M1 p°ijímá L a M2 p°ijímá L M1 a M2 následovn¥. Na vstupu x bude T soub¥ºn¥ simulovat chod obou stroj·. Provede vºdy st°ídav¥ jednu instrukci stroje M1 se vstupem x a jednu instrukci stroje M2 se vstupem x. Jeden ze simulovaných stroj· se po kone£ném po£tu krok· zastaví a p°ijme sv·j vstup. Stroj T podle toho, který stroj vstup p°ijal, odpoví 1 nebo 0. Naopak, jsou-li
Následující tvrzení poskytuje motivaci pro název recursively enumerable .
Tvrzení 3.8.
Pro jazyk L jsou následující podmínky ekvivalentní: • L je rekursivn¥ spo£etný, • L je oborem hodnot n¥jaké £áste£né rekursivní funkce, • L je oborem hodnot n¥jaké úplné rekursivní funkce,
simulované výpoèty
SLOITOST PRO KRYPTOGRAFII
S(a1 ) S(a2 )
9
kroky výpoètù stroje S 1 2 i
S(aj ) S(ai )
výpis aj (S(aj ) = 1)
Obrázek 1. Schéma výpo£tu Turingova stroje
D·kaz.
Nech´ je jazyk
L ⊂ Σ∗
rekursivn¥ spo£etný a
M.
S ∈ DTM
ho p°ijímá. Nech´
Σ∗ = {a1 , a2 , . . . } je n¥jaké efektivní o£íslování. Zkonstruujeme stroj
L.
M
jehoº oborem hodnot bude
B¥h stroje je znázorn¥n na obrázku 1.
M na jednotlivá kola. V prvním kole bude stroje M S se vstupem a1 . V druhém kole stroje se bude simulovat druhý krok výpo£tu S(a1 ) a první krok výpo£tu S(a2 ). V i-tém kole se tedy bude po£ítat i-tý krok výpo£tu S(a1 ), (i−1)-ní krok S(a2 ) atd. aº po první krok výpo£tu S(ai ). Na obrázku 1 jsou jednotlivá kola stroje M vyzna£ena jako tu£né diagonální ²ipky. V k -tém °ádku (k ≥ 1) jsou znázorn¥ny kroky stroje S se vstupem ak . Simulace jednoho kroku výpo£tu stroje S je vyzna£ena krouºkem. Pokud nastane S(aj ) = 1 pro n¥jaké j ≥ 1 v i-tém kole výpo£tu stroje M , pak se slovo aj vypí²e a v následujících kolech stroje M se jiº výpo£et S(aj ) nesimuluje (na obrázku ozna£eno Rozd¥lme výpo£et stroje
simulovat první krok stroje
k°íºkem).
M prochází v²echna slova nad abecedou Σ a platí inkluze L ⊆ Σ∗ , musí být kaºdé x ∈ L po kone£ném po£tu krok· stroje M nalezeno. Nyní jiº snadno de nujeme výstup stroje M na vstupu i ∈ N. M bude po£ítat tak dlouho, aº najde i slov z jazyka L. Poslední z nich bude jeho výstupem. Je z°ejmé, ºe M po£ítá Protoºe stroj
úplnou rekursivní funkci. Ta je sou£asn¥ triviáln¥ i £áste£nou rekursivní funkcí.
L, pak lze M získávat diagonální metodou (analogicky jako v d·kazu první £ásti) v²echna slova jazyka L od stroje S . Tato slova bude porovnávat se slovem x. Platí-li x ∈ L, pak se stroj M po kone£ném po£tu krok· zastaví a odpoví správn¥. Stroj M tedy p°ijímá jazyk L a jazyk L je rekurzivn¥ spo£etný. Zbývá ukázat, ºe existuje-li Turing·v stroj
zkonstruovat stroj
M,
který jazyk
L
S,
jehoº obor hodnot je
p°ijímá. P°i dotazu
x∈L
za£ne
4. Nedeterministické stroje Na Turingovy stroje se díváme jako na nástroje, umoº¬ující efektivn¥ vy°e²it n¥jaký problém. Takový pohled je ale oprávn¥ný jen pro deterministické stroje. Pro nedeterministické stroje nejen není jasné, jak je prakticky realizovat, není dokonce jasné ani to, co povaºovat za jejich výstup. Na daném vstupu totiº m·ºe existovat mnoho r·zných výpo£t·, tedy také mnoho výsledk·, relace symbol
T (x)
δT∗
nede nuje funkci a
nedává dobrý smysl.
Jak tedy chápat nedeterministické výpo£ty? Odpov¥¤ dává následující zásadní de nice.
10
T
PÁN HOLUB
De nice 4.1. na vstupu
x
ekneme, ºe nedeterministický stroj
existuje
alespo¬ jeden
ekneme, ºe nedeterministický stroj
x,
práv¥ kdyº
A p°ijímá vstup x,
práv¥ kdyº
p°ijímající výpo£et.
A p°ijímá
jazyk
L,
pokud
A
p°ijímá vstup
x ∈ L.
Je d·leºité si uv¥domit, ºe de nice p°ijímání vstupu nedeterministickým strojem je nekonstruktivní, mluví o existenci p°ijímajícího výpo£tu, ne°íká ale nic o tom, jak takový výpo£et najít, nebo jak s pomocí daného nedeterministického stroje v·bec zjistit, zda existuje. Jedna z moºností, z my²lenkového hlediska nejjednodu²²í, ale £asov¥ náro£ná, je projít v²echny moºné výpo£ty; o tom mluví V¥ta 7.4. Fungování nedeterministického stroje si lze ilustrovat na Tvrzení 3.8. Je-li dán deterministický stroj algoritmus p°ijímající
• • •
vstup
M L
s oborem hodnot
L,
m·ºeme de novat nedeterministický
takto:
x;
nedeterministicky zvol pokud
M (i) = x,
i;
p°ijmi.
Postupné prohledávání v²ech výpo£t· pouºité v d·kazu Tvrzení 3.8. je vlastn¥ deterministickou simulací uvedeného nedeterministického algoritmu. V p°ípad¥ nedeterminismu se omezujeme na rozhodovací problémy. Proto se n¥kdy °íká, ºe nedeterministický stroj sv·j jazyk
rozhoduje.
Jak je ale vid¥t i na
p°edchozím p°íkladu, termín p°ijímá lépe vyjad°uje asymetrii mezi p°ijetím a zamítnutím vstupu. Nedeterministický stroj m·ºe na vstupu z p°ijímaného jazyka umoº¬ovat mnoho výpo£t·, které nekon£í p°ijetím; to ale neznamená zamítnutí. Vstup je zamítnut , jen pokud neexistuje
ºádný
p°ijímající výpo£et.
5. Sloºitostní t°ídy Dosud jsme se zabývali jen otázkou, zda je daný problém v·bec algoritmicky °e²itelný. Na²ím hlavním tématem v²ak bude otázka, jak
sloºité
je °e²ení daného
°e²itelného problému. Nejprve de nujeme t°ídy funkcí, jimiº budeme sloºitost m¥°it.
De nice 5.1.
ekneme, ºe funkce
takové, ºe pro v²echna
f
leºí v
O(g),
pokud existuje
c > 0
n∈N f (n) < c · g(n).
ekneme, ºe funkce
f
leºí v
o(g),
lim
n→∞ ekneme, ºe funkce ekneme, ºe funkce ekneme, ºe funkce
f f f
leºí v leºí v leºí v
V literatu°e se £asto namísto
pokud
f (n) = 0. g(n)
θ(g), pokud f ∈ O(g) a Ω(g), pokud g ∈ O(f ). ω(g), pokud g ∈ o(f ).
f ∈ O(g)
pí²e
f = O(g)
sou£asn¥
g ∈ O(f ).
(a podobn¥ pro ostatní
symboly).
f (n) ∈ O(g) je ekvivalentní tvrzení, ºe existuje konstanta f (n) < c · g(n) platí pro v²echna n > n0 .
V²imn¥te si, ºe de nice
c
a
n0 ∈ N
takové, ºe
Hlavními m¥°ítky náro£nosti daného výpo£tu je spot°eba £asu a prostoru. Náro£nost je vºdy
funkcí délky vstupu.
De nice 5.2.
Nech´
stroje
A
na vstupu
A ∈ TM. Ozna£me t0A (x) maximální po£et krok· výpo£tu x ∈ Σ∗ (o maximálním po£tu krok· hovo°íme proto, ºe stroj
SLOITOST PRO KRYPTOGRAFII je obecn¥ nedeterministický).
asová náro£nost
11 algoritmu
A
je funkce
tA : N → N ,
kde
tA (n) = max {t0A (x)}. |x|=n
s0A (x) maximální po£et nav²tívených x. Prostorová náro£nost algortimu je funkce
Podobn¥ ozna£me na vstupu
polí£ek b¥hem výpo£tu
sA (n) = max {s0A (x)}. |x|=n
K prostorové náro£nosti viz De nici 6.2.
De nice 5.3.
P leºí v TIME (f ) (resp. NTIME (f )), pokud A ∈ DTM (resp. ∈ NTM), který ho °e²í, a platí tA ≤ f . Je-li F t°ída funkcí, pí²eme P ∈ TIME (F ), pokud P ∈ TIME (f ), pro n¥jakou funkci f ∈ F . Analogicky de nujeme t°ídu problém· NTIME (F ), SPACE (f ), NSPACE (f ), SPACE (F ) p°ípadn¥ NSPACE (F ). ekneme, ºe problém
existuje algoritmus
Protoºe jsme
t0A (x)
v De nici 5.2 ur£ili jako
maximální
z moºných výpo£t·,
musejí v nedeterministickém p°ípad¥ v daném £ase skon£it v²echny moºné výpo£ty, bez ohledu na jejich výsledek (nap°. polynomiální nedeterministický stroj se tedy v polynomiálním £ase zastaví
vºdy ).
O algoritmu, který ve vý²e uvedených de nicích musí existovat, aby problém, který °e²í, leºel ve t°íd¥
C,
°ekneme, ºe t°íd¥
C odpovídá.
P°estoºe jsou p°edchozí
de nice formulovány pro obecné problémy, budeme je pouºívat p°edev²ím pro problémy rozhodovací. Pokud °ekneme, ºe n¥jaký jazyk leºí v t°íd¥ je rozhodován n¥jakým
A ∈ TM,
který odpovídá
C,
znamená to, ºe
C.
N¥které d·leºité sloºitostní t°ídy mají zvlá²tní jména.
De nice 5.4. P=
[
TIME nk = TIME nO(1)
k≥1
NP =
[
NTIME nk = TIME nO(1)
k≥1
EXP =
[
k O(1) TIME 2n = TIME 2n
k≥1
E=
[
TIME 2kn = TIME 2O(n)
k≥1
NEXP =
[
O(1) NTIME (k n ) = NTIME 2n
k≥1
L = SPACE (log(n)) NL = NSPACE (log(n)) [ PSPACE = SPACE nk = SPACE nO(1) k≥1
NPSPACE =
[
NSPACE nk = NSPACE nO(1)
k≥1 Nejd·leºit¥j²í je t°ída
P,
protoºe algoritmy, které pracují v polynomiálním £ase,
P se proto n¥kdy A ∈ TM pracující v polynomiálním £ase budeme jednodu²e ozna£ovat jako polynomiální algoritmus. ¯ leºí v C . Je-li C t°ída jazyk·, pak coC zna£íme t°ídu jazyk· L, jejichº dopln¥k L
jsou tradi£n¥ povaºovány za pouºitelné v praxi. Problémy v ozna£ují jako
zvládnutelné.
Algoritmus
12
T
PÁN HOLUB 6. Realisti£t¥j²í výpo£etní modely Popsaný Turing·v stroj má velmi jednoduchý popis, coº je výhodné pro zkou-
mání jeho vlastností, ale znesnad¬uje to psaní program· , tj. tvorbu Turingových stroj· realizujících n¥jaký algoritmus, který máme popsán slovn¥, v pseudokódu nebo n¥jakém sou£asném programovacím jazyce. P°edpokládejme nap°., ºe v pr·b¥hu výpo£tu chceme pouºívat po£ítadlo po£tu dosud provedených krok·. Takové po£ítadlo je moºné realizovat vyhrazením £ásti pásky, coº v²ak p°iná²í komplikace. Nevíme-li p°edem, jak velké £íslo na po£ítadle budeme pot°eba zapsat, budeme muset v pr·b¥hu programu prostor pro po£ítadlo zv¥t²ovat. To lze posouváním symbol· realizovat, ale je to komplikace, která se skute£nou povahou algoritmu nemá nic spole£ného. V této kapitole proto zavedeme pohodln¥j²í výpo£etní modely. Tím ov²em vznikne otázka, vzhledem k jakému modelu uvaºujeme na²e sloºitostní t°ídy. D·leºitým výsledkem bude, ºe £asové i prostorové nároky jednotlivých model· jsou svázány polynomiáln¥. Z toho plyne, ºe t°ída
P
je na pouºitém modelu nezávislá. To by
neplatilo nap°. pro t°ídu algoritm· pracujících v lineárním £ase. To je dal²í d·vod, pro£ je t°ída
6.1.
P
hlavním p°edm¥tem teoretického zájmu.
Vícepáskové Turingovy stroje.
Problém s po£ítadlem se nejlépe vy°e²í tím,
ºe stroji p°idáme jednu pásku, která bude vyhrazena jen pro po£ítadlo. Takto m·ºeme p°idávat i dal²í pásky pro jednotlivé úkoly programu. To vede k de nici vícepáskového stroje. Je to stroj podobný oby£ejnému Turingovu stroji opat°ený páskami a
k
k
hlavami. V jednom kroku se provede standardní krok Turingova stroje
na v²ech páskách sou£asn¥. V tomto p°ípad¥ je p°irozené povolit, aby daná hlava z·stala na svém míst¥. Matematicky dostáváme následující de nici.
De nice 6.1.
k -páskový Turing·v stroj je £tve°ice (Q, Σ, qs , P ), P je n¥jaká mnoºina
kde
Σ, Q
a
M
jsou jako v De nici 2.1 a program
P ⊆ Q × Σk × Q × Σk × M k . Jedna instrukce
k -páskového *
q,
s1 . . .
stroje má tedy tvar
0 ,q ,
sk Uv¥domte si, pro£ v de nici není
Qk ,
s01
m1
. . .
,
. . .
s0k
+ .
mk
v²echny hlavy mají jeden spole£ný stav.
Q je libovolná Q1 × Q2 × · · · × Ql . Mluvíme-li o k -páskovém Turingov¥ stroji se vstupem a výstupem, rozumíme tím
Jeden stav stroje m·ºe kontrolovat v²echny hlavy sou£asn¥. Mnoºinu kone£ná mnoºina. Nic nebrání tomu, aby byla nap°. rovna
k -páskový
Turing·v stroj, jehoº první páska je pouze vstupní, stroj na ní nem·ºe
p°episovat symboly (ale m·ºe se pohybovat v obou sm¥rech), a poslední páska je výstupní, stroj m·ºe psát na prázdná polí£ka, ale nem·ºe p°episovat ani se vracet. Na zbylých
k−2
pásek neklademe ºádná omezení a nazýváme je
pracovní.
Vícepáskový stroj budeme chápat vºdy jako stroje se vstupem a výstupem. Na za£átku výpo£tu je vstup napsán na vstupní pásce, hlava vstupní pásky je na po£átku vstupu a ostatní pásky jsou prázdné. asová náro£nost vícepáskového stroje je de nována obdobn¥ jako u jednopáskového stroje. Pro prostorovou sloºitost up°esníme De nice 5.2 a 5.3.
SLOITOST PRO KRYPTOGRAFII
De nice 6.2.
Prostorovou sloºitost
13
problému m¥°íme vzhledem k vícepáskovému
stroji, p°i£emº prostorovou náro£ností výpo£tu rozumíme po£et nav²tívených polí£ek na pracovních páskách. Vstupní a výstupní páska se tedy p°i m¥°ení prostorové náro£nosti nebere v úvahu. To umoº¬uje uvaºovat stroje, které mají men²í prostorovou náro£nost, neº je délka vstupu (nap°íklad nulovou - to jsou tzv. kone£né automaty). Bez takového p°ístupu by nap°íklad t°ída
L nedávala smysl. V²imn¥te si, ºe v de nici nebylo nutné
ur£ovat po£et pásek, protoºe více pásek lze na jedné pásce simulovat se stejnou prostorovou náro£ností (navíc jsou pouze odd¥lova£e pásek, coº na sloºitostní t°ídu nemá vliv díky Tvrzení 7.1 o lineárním zrychlení).
V¥ta 6.3.
Je-li n¥jaký problém P v TIME (f (n)) pro k -páskový Turing·v stroj, pak je v TIME O(f (n)2 ) pro jednopáskový Turing·v stroj.
D·kaz.
Ukáºeme, jak na jednopáskovém stroji simulovat b¥h
Ozna£me jednopáskový stroj Páska stroje
J
J
a
k -páskového
stroje.
k -páskový K .
bude po °ad¥ obsahovat nav²tívené úseky jednotlivých pásek
odd¥lené novým symbolem $, v£etn¥ informace o poloze hlavy. Má tedy podobu $ obsah 1. pásky $ obsah 2. pásky $ . . . $ Popí²eme simulaci jednoho kroku stroje
K.
obsah
k -té
pásky $.
Hlava projede celou pásku zleva do-
prava a zapamatuje si £tené symboly na jednotlivých páskách
(s1 , . . . , sk ). Sou£asn¥
zkontroluje, zda se hlava na n¥jaké pásce nenachází na krajní pozici vlevo nebo vpravo (tedy v t¥sné blízkosti symbolu $). Pokud taková situace nastane, posune celý obsah své pásky tak, aby vytvo°ila místo pro p°ípadný pohyb p°íslu²né hlavy na dosud nenav²tívené polí£ko. To je moºné zvládnout jedním projetím. Pak se hlava vrátí a cestou zp¥t provede p°íslu²né instrukce, tedy zm¥ní symboly
s1 , . . . , sk
na symboly
s01 , . . . , s0k
m1 , . . . , mk .
a provede pohyby
Celkem tedy pro
realizaci jednoho kroku projede dvakrát svou pásku. Kaºdá z díl£ích pásek má délku maximáln¥ po
f (n)
f (n),
nebo´ výpo£et stroje
K
skon£í
krocích a v kaºdém kroku se m·ºe zaplnit maximáln¥ jedno nové polí£ko.
J je tedy celkov¥ maximáln¥ k f (n) + (k + 1). K simulaci k -páskového stroje musí tedy stroj jednopáskový vykonat maximáln¥ 2k(f (n) + c) krok·, kde c je n¥jaká konstanta vyjad°ující kroky nutné k simulaci
Délka pouºité pásky jednoho kroku
zm¥n na jednotlivých páskách (hlava se ob£as musí vrátit o jedno polí£ko).
K provede O(f (n)2 ).
Jestliºe tedy stroj stroje 6.2.
J
leºet v
Stroje RAM.
b¥hem výpo£tu
f (n)
krok·, bude po£et krok·
Nejv¥t²í omezení Turingových stroj· v porovnání s na²í p°ed-
stavou o práci skute£ných po£íta£· je skute£nost, ºe chceme-li zjistit obsah n¥jakého vzdáleného polí£ka, musí hlava projet celou vzdálenost. Skute£ný po£íta£ má p°ímý p°ístup k bu¬ce pam¥ti, jejíº adresu zná. Výpo£etní model, který se v tomto smyslu podobá skute£nému po£íta£i, se nazývá
RAM
(Random Access Machine).
registry, které mohou obsahovat registrového stroje ). Registr· je ne-
Polí£ka pásky jsou v tomto modelu nahrazena libovolné celé £íslo (RAM je tedy druh tzv.
kone£n¥ mnoho a jsou o£íslovány nezápornými celými £ísly, která budeme nazývat
adresy. Nultý registr funguje jako pracovní, nazývá se také n¥kdy akumulátor. i-tého registru budeme zna£it [i]. D·leºitou vlastností RAM je schopnost nep°ímého adresování, tedy moºnost
jejich
Obsah
pracovat s registrem, jehoº adresa je obsahem jiného registru. To lze snadno napsat
[[i]]: obsah registru, jehoº adresa je obsaºena v i-tém registru. RAM má dále vstupní a výstupní kanál, které m·ºeme chápat
jako
jako zvlá²tní
registry schopné obsahovat kone£né posloupnosti celých £ísel, p°i£emº ze vstupního
14
T
PÁN HOLUB
kanálu je moºné pouze £íst (kaºdý prvek posloupnosti nejvý²e jednou a jeden po druhém), do výstupního kanálu lze pouze psát.
po£ítadlo, které °ídí výpo£et, hodnotu po£ítadla buκ. Výpo£et RAM je, podobn¥ jako u TM, de nován programem.
Zvlá²tním registrem je dále deme ozna£ovat
Program RAM
je o£íslovaná posloupnost instrukcí, které m·ºeme rozd¥lit do £ty°
skupin:
•
vstup a výstup:
Input
READ j
zapi² dal²í prvek vstupu do registru
[j] → Output
PRINT j •
→ [j]
vytiskni obsah
j -tého
registru
komunikace pracovního registru s pam¥tí:
STORE j
[0] → [j]
STORE ↑ i
[0] → [[i]]
uloº obsah pracovního registru do
LOAD j
[j] → [0]
LOAD ↑ i
[[i]] → [0]
registru
nahraj obsah
i-tého
i
registru do pracovního registru
nahraj do pracovního registru obsah registru, jehoº adresa je uloºena v registru
i → [0]
LOAD = i
i-tého
uloº obsah pracovního registru do registru, jehoº adresa je uloºena v registru
•
j
i
zm¥¬ hodnotu pracovního registru na
i
aritmetické operace:
[0] + [j] → [0]
ADD j
p°i£ti obsah
i-tého
registru do pracovního re-
gistru
ADD ↑ j
[0] + [[j]] → [0]
p°i£ti do pracovního registru obsah registru, jehoº adresa je obsaºena v registru
[0] − [j] → [0]
SUB j
j
ode£ti obsah i-tého registru od pracovního registru
SUB ↑ j
[0] − [[j]] → [0]
ode£ti od pracovního registru obsah registru, jehoº adresa je obsaºena v registru
b[0]/2c → [0]
HALF
j
odstra¬ nejmén¥ významný bit pracovního registru
• °ízení JUMP j
toku instrukcí
HALT
κ := j
jdi na instrukci
j
κ := 0
zastav se (lze nahradit skokem na libovolnou neexistující instrukci)
POS j
if [0] > 0 then κ := j
je-li obsah pracovního registru kladný, jdi na instrukci
NEG j
if [0] < 0 then κ := j
je-li obsah pracovního registru záporný, jdi na instrukci
ZERO j
if [0] = 0 then κ := j
j j
je-li obsah pracovního registru nula, jdi na instrukci
j
Výpo£et je zahájen instrukcí jedna a vykonává instrukce programu popo°ad¥, pokud °ídící instrukce neur£í jinak. Provádí se tedy vºdy instrukce instrukce zv¥t²í
κ
Také v p°ípad¥
κ a kaºdá ne°ídící
o jedna.
RAM
existuje celá °ada r·zných konvencí týkajících se zejména
zp·sobu manipulace s pam¥tí, které nemají na vlastnosti zásadní vliv. D·leºitá je ov²em de nice aritmetických operací, které stroj m·ºe provést v jednom kroku.
SLOITOST PRO KRYPTOGRAFII
15
Pokud nap°. dovolíme v jednom kroku násobit obsah registr·, výkon stroje se zvý²í výce neº konstantn¥ (pak se n¥kdy mluví o
MRAM).
Podobn¥ m·ºeme uvaºovat
o dal²ích operacích. Délku zápisu £ísla
a
ozna£me
d(a).
Délka vstupu je sou£et délek £ísel ve v²ech
registrech, p°i£emº nula má nulovou délku. (Uvaºujme nap°íklad dyadický zápis £ísel s jedním bitem rezervovaným pro znaménko.) Operace s£ítání, od£ítání a d¥lení dv¥ma, které jsme dovolili v na²í de nici, mají tu vlastnost, ºe jejich skute£ná náro£nost je lineární v délce zápisu, tedy leºí v
log k ,
kde
k
je v¥t²í z operand·.
RAM. První z nich, jednotková cena (unit cost ), po£ítá pouze po£et provedených instrukcí, nich, logaritmická cena (logarithmic cost ), bere v úvahu i délku zpraco-
Existují dva základní p°ístupy k m¥°ení sloºitosti výpo£tu nazývaná druhá z
vávaných £ísel a provedení aritmetických instrukcí má cenu p°ímo úm¥rnou délce v¥t²ího z operand·. Faktory logaritmické velikosti jsou tedy obzvlá²´ závislé na p°ijatém modelu, coº m·ºe být zdrojem r·zných nedorozum¥ní, pokud se zabýváme sloºitostními t°ídami, které nejsou dostate£n¥ robustní. Podobn¥ je to s otázkou za£len¥ní násobení mezi elementární instrukce. T°ída
P
je v²ak v·£í v²em uvedeným
moºnostem invariantní. Pro ú£ely simulace
RAM
Turingovým strojem je nutné uvaºovat logaritmickou
cenu, jednotková cena není realistická. Následující tvrzení omezuje délku £ísel, která se v pr·b¥hu výpo£tu m·ºou v registrech objevit.
Lemma 6.4.
Po t krocích stroje RAM je délka libovolného registru d(ri ) nejvý²e t + d(I) + d(k), kde d(I) je délka vstupu a d(k) je délka nejdel²í konstanty obsaºené v programu. D·kaz. • •
t = 0.
Tvrzení platí pro
P°edpokládejme, ºe tvrzení platí pro
t − 1.
P°íkazy JUMP, POS, NEG, ZERO a HALT obsahy registr· nem¥ní. P°íkazy LOAD a STORE p°esouvají obsah z registru do registru a tvrzení pro n¥ tedy platí.
•
P°íkaz READ na£ítá obsah vstupu, jehoº délka je v odhadu zastoupena s£ítancem
• •
d(I).
P°íkaz HALF obsah registru zkracuje. P°íkazy ADD a SUB s£ítají dv¥ celá £ísla
a
a
b,
pro n¥º podle induk£ního
p°edpokladu platí
d(a), d(b) ≤ t − 1 + d(I) + d(k). Sta£í uváºit, ºe
d(a + b)
je nejvý²e
max{d(a), d(b)} + 1.
V¥ta 6.5.
Jestliºe je n¥jaký problém v TIME (f (n)) pro RAM, pak je v TIME f (n)3 pro 6-páskový Turing·v stroj. D·kaz.
M je 6-páskový Turing·v stroj, kterým simulujeme výpo£et RAM. RAM jsou za£len¥ny do stav· M v£etn¥ stavu po£ítadla. • První páska stroje M je vstupní. • Druhá slouºí k reprezentaci registr·, krom¥ nultého. Sestává z posloupnosti °et¥zc· ve tvaru b(i) : [b(i)], kde b je n¥jaká permutace na mnoºin¥ inNech´
Instrukce
dex· registr·, se kterými se jiº pracovalo. Jednotlivé registry jsou odd¥leny speciálním znakem.
• •
Na t°etí pásce je zaznamenána adresa práv¥ hledaného registru. tvrtá páska obsahuje pracovní registr a jsou na ní provád¥ny aritmetické operace.
•
Pátá páska je výstupní.
16
T
PÁN HOLUB P°i hledání registru
b(i) = j ,
Pokud
je
[b(i)]
j
se z druhé pásky postupn¥ na£ítají dvojice
b(i) : [b(i)].
zpracováno podle typu provád¥né instrukce.
P°i jakékoli zm¥n¥ registru se jeho zápis v °ad¥ registr· smaºe a zapí²e znovu na konec. (Tím se vyhneme úvahám o posouvání obsahu a vytvá°ení místa pro dlouhé registry.) Nyní ukáºeme, ºe £asová náro£nost simulace jednoho kroku govým strojem je
O(f (n)2 ),
kde
n
RAM
na²ím Turin-
je délka vstupu.
asov¥ nejnáro£n¥j²í je aritmetická instrukce s nep°ímým adresováním, kdy je pot°eba dvakrát prohledat druhou pásku (poprvé pro nalezení registru registru
j
a poté
[j]).
Druhá páska obsahuje
O(f (n))
dvojic (v£etn¥ smazaných úsek·). Délka kaºdé
dvojice je podle p°edchozího lemmatu také
O(f (n)).
V²imn¥me si zejména, ºe ad-
resy pouºitých registr· také podléhají omezení z lemmatu. Pouºitý prostor pásky s registry je tedy v pr·b¥hu celého výpo£tu omezen vyºaduje
2
O(f (n) )
krok· stroje
O(f (n)2 )
a jeho prohledání
M.
Aritmetické operace (ADD, SUB, HALF) pracují s £ísly délky výpo£et lze tedy provést v £ase
O(f (n)3 )
O(f (n)).
Celkem tedy stroj
M
O(f (n)),
a jejich
p°i simulaci vykoná
krok·.
7. Vztahy mezi t°ídami
Tvrzení 7.1 (Lineární zrychlení).
Nech´ L ∈ TIME (f (n)) a L ∈ SPACE (g(n)). Pak také L ∈ TIME (εf (n)) a L ∈ SPACE (εg(n)) pro kaºdé ε > 0. D·kaz.
M ∈ TM odpovídající t°ídám TIME (f (n)) a SPACE (g(n)). M 0 odpovídající t°ídám TIME (εf (n)) a TIME (εg(n)). 0 Bu¤ k p°irozené £íslo, které ur£íme pozd¥ji. Rychlost stroje M bude spo£ívat v tom, ºe v jednom cyklu sestávajícím z n¥kolika krok· nasimuluje k krok· stroje M . 0 0 Mnoºina symbol· Σ stroje M obsahuje v²echny k -tice symbol· Σ stroje M . Tedy M¥jme
Zkonstruujeme stroj
Σ0 = Σk . M0
Obsah pásky stroje skupené do stroje
M0
je tedy
Hlava stroje polohu). Po
k
M0
M
se-
ºe i vstup je takto zadán). Prostorová náro£nost
g(n) . k
k -tici, která obsahuje hlavu stroje M (a pamatuje si její M se tedy m·ºe zm¥nit pouze k -tice £tená a její pravý zm¥na je t¥mito k -ticemi jednozna£n¥ zadána. Instrukce stroje £te
krocích stroje
nebo levý soused a
M0
obsahuje v kaºdé fázi výpo£tu obsah pásky stroje
k -tic (p°edpokládáme, m l
tedy vytvo°íme tak, aby stroj v jednom cyklu
•
p°e£etl levého nebo pravého souseda £teného polí£ka, pokud se stane, ºe hlava simulovaného stroje tohoto souseda v rámci uvaºovaných
k -krok·
nav²tíví;
•
zasaºená polí£ka (odpovídající nejvý²e aby odpovídala stavu pásky stroje
•
zastavil se v
k -tici
obsahující po
k
M
2k polí£k·m k krocích;
stroje
M)
zm¥nil tak,
po
krocích hlavu stroje
M.
Snadno si rozmyslíme, ºe k tomu sta£í t°i kroky. asová náro£nost stroje tedy nejvý²e
l
m
3 f (n) . Nyní sta£í nap°. zvolit k
k=
6
ε .
M0
je
P°edchozí v¥ta nás oprav¬uje k tomu, abychom ve sloºitostních funkcích nebrali ohled na konstanty. M·ºeme tedy nap°. místo
TIME (O(f )) psát pouze TIME (f )
Ukazuje se, ºe ne v²echny funkce jsou vhodné pro ur£ování sloºitosti. Jak uvidíme, problém m·ºe být s funkcemi, které je obtíºné spo£ítat.
SLOITOST PRO KRYPTOGRAFII
De nice 7.2.
Funkce
f (n)
je
17
£asov¥ (prostorov¥) konstruovatelná, pokud existuje n pot°ebuje nejvý²e f (n)
Turing·v stroj, který ji po£ítá a pro výpo£et se vstupem krok· (prostor nejvý²e
f (n)).
V²echny p°irozené funkce jsou konstruovatelné, de nice slouºí pouze k vylou£ení jistých patologických p°ípad·, viz Tvrzení 7.10. V²imn¥me si také pon¥kud
f
opatrné formulace. Pokud bychom °ekli, ºe konstruovatelná funkce s výpo£etní náro£ností
f,
je spo£itatelná
mohlo by dojít k nedorozum¥ní. Výpo£etní náro£nost se
totiº m¥°í délkou vstupu, který je typicky logaritmický vzhledem k velikosti £ísla. Poºadavek na konstruovatelnou funkci je tedy velmi volný, p°i binárním zápisu vstupu má algoritmus exponenciální £as (prostor) vzhledem k velikosti vstupu. V p°ípadech, kdy chceme náro£nost m¥°it velikostí £ísla, nikoli velikostí jeho zápisu,
n je reprezentováno vstupem 1n . Mohli bychom funkce, pokud je spo£itatelná s náro£ností f p°i
se n¥kdy pouºívá unární zápis: £íslo tedy °íci, ºe
f
je konstruovatelná
unárním vstupu. Nejprve si uv¥domme triviální vztahy mezi t°ídami.
Tvrzení 7.3. (1) (2) (3)
D·kaz.
Pro jednotlivé t°ídy sloºitosti platí: TIME (f (n)) ⊆ SPACE (f (n)) TIME (f (n)) ⊆ NTIME (f (n)) SPACE (f (n)) ⊆ NSPACE (f (n)) (1) Stroj
M
nem·ºe za £as
f (n)
f (n)
nav²tívit více neº
polí£ek na
pásce. (2) a (3) Deterministický stroj je také nedeterministický stroj.
D·leºitou otázkou je moºnost deterministického výpo£tu deterministickým strojem. Nejprve ukáºeme, ºe nedeterministický £as lze simulovat stejn¥ velkým deterministickým prostorem. Základní my²lenkou takové simulace bude cující
vektor voleb.
po£ítadlo
zachy-
Tvrzení 7.4. NTIME (f (n)) ⊆ SPACE (f (n)) .
D·kaz.
Chceme simulovat b¥h nedeterministického stroje
tickým strojem
M 0.
M
n¥jakým determinis-
Budeme bez újmy na obecnosti p°edpokládat, ºe simulující
stroj má dv¥ pracovní pásky. Na jedné z nich budeme simulovat výpo£et stroje
M,
na druhé si budeme zaznamenávat, jaké volby mezi r·znými pokra£ováními jsme provedli. Nech´
c
je maximální po£et instrukcí aplikovatelných na jeden okamºitý
popis. M·ºeme pro jednuchost p°edpokládat, ºe voleb je p°esn¥
c
v kaºdém kroku
(p°idáme neexistující volby vedoucí k zastavení a zamítnutí vstupu). Kaºdý výpo£et nedeterministického stroje je dán tzv.
vektorem voleb,
coº je
posloupnost
d1 , . . . , dt , kde
t ≤ f (n) i-tém
zvolil v
je délka výpo£tu a
di
ur£uje, kterou instrukci z
c
moºných si stroj
kroku.
Druhá páska tedy bude obsahovat vektor voleb. Kdykoli simulace jedné z v¥tví výpo£tu stroje
M
skon£í, stroj
M0
zvý²í vektor voleb o jedna. P°esn¥ji °e£eno,
d0t < c, zvý²í ho o jedna a v²echna di , i > t smaºe. Poté simuluje výpo£et nové v¥tve M dané aktuálním vektorem voleb. (Výpo£et kon£í po simulaci, ve které jsou v²echna di = c.) Po£ítadlo celkem spot°ebuje prostor f (n) log c a celková prostorová náro£nost je tedy O(f (n). Nyní sta£í pouºít v¥tu o lineárním zrychlení. provede následující operaci: najde nejv¥t²í
0
t0 ,
pro které je
18
T
PÁN HOLUB Pro ur£ení vztahu nedeterministické prostorové náro£nosti k deterministické je
zásadní problém Dostupnost. Jeho vstupem je orientovaný graf jeho vrcholy
s
a
t.
s
Máme rozhodnout, zda z
do
t
G(V, E)
a dva
vede cesta. (Problém bývá
anglicky nazýván s-t connectivity nebo Stcon.)
Lemma 7.5. D·kaz. z
x
Dostupnost
Budeme psát
y
vede cesta do
∈ SPACE log2 (n) , kde n je po£et vrchol· grafu.
i
x −→ y ,
pokud z
práv¥ tehdy, kdyº
libovolnými dv¥ma vrcholy je nejvý²e
x
do
y
vede cesta délky nejvý²e
dlog ne
x −→ y, n.
2i .
Z°ejm¥
nebo´ délka nejkrat²í cesty mezi
Kaºdou cestu lze rozd¥lit na dv¥ £ásti, které se od sebe li²í nejvý²e o jednu. Pro
i>0
tedy platí tedy, ºe
i
x −→ y ,
práv¥ kdyº existuje n¥jaký vrchol
z
(st°ed cesty),
pro n¥jº
i−1
i−1
x −→ z ∧ z −→ y. A(x, y, i), který vrcholy z a zjistí, zda
Na základ¥ tohoto poznatku popí²eme algoritmus
i
x −→ y .
Pokud
i > 1,
algoritmus projde v²echny
zjistí, zda
A(x, z, i − 1) ∧ A(z, y, i − 1). Pokud
i = 0,
zjistí, zda
(x, y) ∈ E nebo x = y. log(n) a prostor k uloºení jedné úrovn¥ je k log(n), kde k je n¥jaká konstanta (délka zápisu jednoho vrcholu je nejvý²e dlog(n)e). Tedy 2 celková prostorová náro£nost je v O(log (n)).
Hloubka rekurze algoritmu bude
Tvrzení 7.6
(Savitchova v¥ta)
log n. Pak
D·kaz.
.
Bu¤ f prostorov¥ konstruovatelná funkce, f (n) ≥
NSPACE (f (n)) ⊆ SPACE f (n)2 .
L ∈ NSPACE (f (n)) a nech´ M ∈ TM je (nedeterministický) TuL rozhoduje. Chceme ukázat, ºe existuje deterministický stroj 2 rozhodující L v prostoru f (n) . Klí£em k d·kazu je fakt, ºe pro dané x platí x ∈ L, práv¥ kdyº existuje posloupnost snímk· stroje M , která de nuje p°ijímající výpo£et pro vstup x. Abychom toto vyuºili, uvaºujme orientovaný graf GS , jehoº vrcholy jsou v²echny moºné snímky stroje M a z vrcholu σ1 vede hrana do vrcholu σ2 práv¥ tehdy, kdyº Nech´
ring·v stroj, který
δ
M σ1 −→ σ2 ,
neboli pokud
M.
σ2
je snímek, který vznikne ze snímku
σ1
po jednom kroku stroje
M·ºeme p°edpokládat, ºe existuje práv¥ jeden akceptující snímek, ozna£me ho
ANO . Snímek se vstupem Nyní tedy platí vstup
x
log2 n,
kde
x∈L
x
p°ed za£átkem výpo£tu ozna£me vstup
práv¥ tehdy, pokud v grafu
GS
x .
existuje cesta z vrcholu
do vrcholu ANO . Problém dostupnosti je p°itom °e²itelný v prostoru
n
je po£et vrchol· grafu.
Po£et vrchol· grafu je dán
• •
velikostí mnoºiny stav·
|Σ| • •
QM
stroje
M,
po£tem moºných slov zapsaných na pracovní pásce délky nejvý²e
f (n)
,
f (n), n.
po£tem poloh hlavy na pracovní pásce: po£tem poloh hlavy na vstupní pásce:
Celkem je tedy po£et vrchol·
f (n)
|V | = nf (n) |QM | |Σ|
a
log |V | = log n + log(f (n)) + log |QM | + f (n) log |Σ|, coº je pro
f (n) ≥ log n
v
O(f (n)).
f (n):
SLOITOST PRO KRYPTOGRAFII
19
Existenci cesty je proto moºné zjistit v prostoru
O(f (n)2 ).
Zbývá vysv¥tlit, jakým zp·sobem bude deterministický stroj s grafem
GS
pra-
covat. Je z°ejmé, ºe ho nem·ºe celý vypsat, protoºe tím by p°ekro£il sv·j pracovní prostor. Procházení v²ech vrchol· (snímk·) se bude dít v maximo-lexikogra ckém po°adí. M·ºeme bez újmy na obecnosti uvaºovat v²echny posloupnosti pat°i£né délky, které ani nemusí být zápisem n¥jakého snímku. (Zde pouºíváme p°edpoklad prostorové konstruovatelnosti funkce
f . Je-li f
prostorov¥ konstruovatelná, stroj
M0
umí spo£ítat délku snímku, aniº by p°ekro£il svou vlastní prostorovou náro£nost.) Ov¥°ování existence hrany mezi vrcholy
σ1
a
σ2
se provede simulací jednoho
kroku p°íslu²ného nedeterministického stroje. Simulace prostorové sloºitosti je £asov¥ náro£ná:
Tvrzení 7.7.
Nech´ f (n) ≥ log n. Pak SPACE (f (n)) ⊆
[
TIME k f (n) .
k>1
D·kaz. Nech´ M ∈ DTM je stroj rozhodující jazyk L s prostorovou náro£ností f (n). Po£et snímk· je (podle diskuse v d·kazu Savitchovy v¥ty) nejvý²e k f (n) pro f (n) n¥jaké k . Pokud stroj provede více neº k krok·, znamená to, ºe n¥jaký snímek se objevil dvakrát, a stroj se tedy zacyklil, protoºe je deterministický. To je spor s p°edpokladem, ºe rozhoduje
L.
Kombinací Tvrzení 7.4 a Tvrzení 7.7 dostáváme
NTIME (f (n)) ⊆ SPACE (f (n)) ⊆
[
TIME k f (n) .
k>1 ádná podstatn¥ lep²í neº exponenciální simulace nedeterministického £asu deterministickým není známa. Následující v¥ty ukazují, ºe hierarchie t°íd sloºitosti je dosti hustá.
Tvrzení 7.8
(O prostorové hierarchii). Nech´ f (n) a g(n) jsou funkce takové, ºe log n ≤ f (n), f (n) ∈ o(g(n)) a g(n) je prostorov¥ konstruovatelná. Pak SPACE (f (n)) je vlastní podmnoºina SPACE (g(n)).
D·kaz. Zkonstruujeme jazyk, který leºí ve t°íd¥ SPACE (g(n)) a neleºí ve SPACE (f (n)). Konstrukce má podobu diagonálního argumentu, tj. vyuºívá
t°íd¥ my²-
lenky b¥hu stroje, který má na vstupu sv·j vlastní kód. Uvaºujme n¥jaké kódování
[M ] kód stroje M . Abychom mohli manipulovat s [M ], budeme uvaºovat slova 1m 0[M ], tzv. pre xové kódy stroje M . Je z°ejmé,
Turingových stroj· a ozna£me délkou
ºe z kaºdého pre xového kódu lze snadno zrekonstruovat kód p·vodní. Slíbený jazyk prostoru
g(n).
L
de nujeme pomocí stroje
Stroj
U
my²lenka d·kazu je následující: Stroj bude výstup stroje
M
U,
který ho rozhoduje a pracuje v
je jistou formou univerzálního Turingova stroje. Základní
U
je schopen v prostoru
pracujícího v prostoru
f (n)
g(n) rozpoznat, jaký
v£etn¥ informace, zda výpo£et
diverguje. Do rozporu s nerozhodnutelností problému HaltingProblem se nedostáváme díky tomu, ºe
U
má garantováno prostorové omezení simulovaného stroje.
Pokud simulace probíhá p°íli² dlouho, pozná stroj
U , ºe se simulovaný stroj zacyklil,
díky svému dodate£nému prostoru, který vyuºije pro po£ítadlo.
U tedy postupuje takto. Na vstupu x rozhodne (v konstantním prostoru), x pre xový kód n¥jakého M , a pokud ano, vymezí si na pásce prostor 21 g(n), 1 pro simulaci pracovního prostoru stroje M a po£ítadlo krok· délky 2 g(n) (tedy 1 g(n) s rozsahem 2 2 krok·). (Zde pouºíváme p°edpoklad prostorové konstruovatelStroj
zda je
nosti!) Zbylý prostor jist¥ sta£í pro pomocné výpo£ty. Stroj
U
dále simuluje výpo£et stroje
jeho kroky. Výstup stroje
U
M
na vstupu
x, tedy M (1m 0[M ]), a po£ítá
je dán následujícími pravidly:
20
T
PÁN HOLUB (a) pokud simulace p°esáhla vymezený prostor, p°ijmi; (b) pokud simulace provedla po£et krok· stroje
M
p°esahující rozsah po£ítadla,
p°ijmi; (c) pokud simulace skon£í bez komplikací, tedy aniº by nastalo (a) nebo (b), odpov¥z opa£n¥ neº
M.
P°edpokládejme nyní, ºe n¥jaký stroj M , který pracuje v prostoru f (n), rozhoduje L = L(U ). Chceme dojít ke sporu, a proto hledáme vstup, na kterém se odpov¥¤ U a M bude li²it. Takovým vstupem bude dostate£n¥ dlouhý pre xový kód stroje M . Uvaºujme tedy vstup x = 1k 0[M ], kde k zvolíme tak, aby
g(|x|) > 8 · f (|x|) log |[M ]| , coº je moºné díky
f (n) ∈ o(g(n)).
V²imn¥me si, ºe prostor vymezený strojem simulaci celého výpo£tu stroje
M
U
pro simulaci je dostate£ný na
v£etn¥ binární reprezentace symbol·
ΣM
a stav·
QM . Protoºe
M
konverguje, platí také, ºe po£et krok· jeho výpo£tu
M
je men²í neº
po£et v²ech jeho moºných snímk·, tedy (viz diskusi v d·kazu Savitchovy v¥ty) mén¥ neº
r = |x| f (|x|) |QM | |ΣM | Z
f (n) ≥ log n
f (|x|)
dostáváme
log(r) < 4f (|x|) log |[M ]| < Z toho plyne, ºe výstup stroje nep°ijímá
L,
.
U
1 g(|x|). 2
se bude °ídit pravidlem (c), coº ukazuje, ºe
spor.
M
Podobný d·kaz následující v¥ty vynecháváme.
Tvrzení 7.9
(O £asové hierarchii). Nech´ f (n) a g(n) jsou funkce takové, ºe n ≤ f (n), f (n) log(f (n)) ∈ o(g(n)) a g(n) je £asov¥ konstruovatelná. Pak TIME (f (n)) je vlastní podmnoºina TIME (g(n)). Následující v¥ta, která platí i pro £asovou sloºitost, se zdá být v rozporu s V¥tou
7.8. To ukazuje na d·leºitost chyb¥jícího p°edpokladu o prostorové konstruovatelnosti.
Tvrzení 7.10 (O meze°e). Pro libovolnou rekursivní funkci r > n existuje rostoucí rekursivní funkce f (n), pro kterou platí SPACE (f (n)) = SPACE (r(f (n))) . To tedy nap°. znamená, ºe existuje rekursivní funkce je identická s t°ídou
D·kaz.
SPACE (f (n)) ⊆ SPACE (r(f (n)))
Inkluze
f (n)
taková, ºe t°ída
f (n) SPACE 22 .
SPACE (f (n))
je z°ejmá. Ukáºeme, ºe m·ºe
nastat i opa£ná inkluze.
M ∈ DTM pracoval v prostoru men²ím neº f (n), nebo f (n). Nech´ G je efektivní £íslování DTM. Ozna£me s(i, x) ∈ N ∪ {∞} prostor spot°ebovaný p°i výpo£tu G(i)(x). Hodnota ∞ se nabývá, pokud výpo£et diverguje (a Chceme, aby kaºdý stroj
v¥t²ím neº
r(f (n)).
Ur£íme hodnotu
to i tehdy, pokud se stroj zacyklí, a celý nekone£ný výpo£et je omezen na kone£ný prostor).
f (n) bude nejmen²í p°irozené £íslo takové, aby platilo • f (n) > f (n − 1) (pro n > 1), • pro kaºdý vstup x délky n a kaºdé i ≤ |x| = n platí, ºe bu¤ s(i, x) ≤ f (n), nebo s(i, x) > r(f (n)).
Hodnota
SLOITOST PRO KRYPTOGRAFII Takové £íslo existuje, protoºe mnoºina hodnot ne£n¥ vzájemn¥ disjunktních interval·
(i, r(i)].
21
s(i, x)
je kone£ná a existuje neko-
Sta£í uvaºovat intervaly
Ij = (rj (1), rj+1 (1)], r1 (1) = r(1) a rj+1 (1) = r(rj (1)). L ∈ SPACE (r(f (n))). Jazyk L je tedy rozhodován n¥jakým strojem G(k) tak, ºe pro libovolné x je s(k, x) ≤ r(f (|x|)). Je-li k ≤ |x|, plyne z de nice funkce f , ºe s(k, x) ≤ f (|x|). Modi kujeme-li stroj G(k) tak, aby vstupy délky mén¥ neº k , kterých je kone£n¥ mnoho, rozhodoval tabulkou uloºenou v programu, tedy s nulovou prostorovou náro£ností, dostáváme L ∈ SPACE (f (n)). Zbývá ov¥°it, ºe funkce f (n) je rekursivní. Popí²eme stroj M , který ji po£ítá. P°edpokládejme, ºe hodnotu f (n − 1) lze spo£ítat (poloºme f (0) = 0). Stroj M postupn¥ probírá v²echna £ísla t v¥t²í neº f (n − 1). Pro kaºdé t, kaºdé i ≤ n a kaºdé x délky n bude simulovat výpo£et G(i)(x) a sou£asn¥ m¥°it prostor spot°ebovaný simulovaným výpo£tem stroje G(i) na vstupu x, dokud nenastane jedna z kde
Nech´ nyní
následujících situací
• • •
výpo£et skon£il, výpo£et se zacyklil (to lze zjistit kontrolou po£tu krok·), prostor pouºitý strojem
G(i)
p°esáhl
r(t).
Pokud výpo£et skon£il a pouºitý prostor je v intervalu
(t, r(t)], stroj M
za£ne postup
t + 1.
znovu s
D·sledek 7.11.
Funkce f (n) z p°edchozí v¥ty není prostorov¥ konstruovatelná. 8. Booleovské formule a obvody
De nice 8.1
.
(Booleovská formule)
Uvaºujme abecedu
Σ = X ∪ {∧, ∨, ¬} ∪ {(, )}, kde
X
je n¥jaká mnoºina prom¥nných (obvykle
nazývá (1) (2) (3) (4)
X = {xi | i ∈ N}). Prvek ϕ ∈ Σ+
booleovská formule, práv¥ kdyº je spln¥na jedna z následujících ϕ∈X ϕ = (¬ψ), kde ψ je booleovská formule, ϕ = (ψ1 ∨ ψ2 ), kde ψ1 a ψ2 jsou booleovské formule, ϕ = (ψ1 ∧ ψ2 ), kde ψ1 a ψ2 jsou booleovské formule.
se
podmínek.
Nehrozí-li nedorozum¥ní, budeme p°i zápisu booleovských formulí £asto vynechávat závorky.
ϕ nazýváme pozitivní literál pokud ϕ ∈ X a negativní literál x ∈ X. Symbolem X|ϕ zna£íme mnoºinu promn¥nných, které se vyskytují ve ϕ. Libovolné zobrazení h : X|ϕ −→ {0, 1} nazveme ohodnocením formule ϕ. Formuli
ϕ = ¬x,
pokud
kde
De nice 8.2.
ekneme, ºe booleovská formule ϕ je ohodnocením h spln¥na, pí²eme h(ϕ) = 1, práv¥ kdyº platí jedna z následujících podmínek. (1) ϕ = x, x ∈ X a h(x) = 1, (2) ϕ = ¬ψ a ψ ohodnocením h spln¥na není, (3) ϕ = (ψ1 ∨ ψ2 ) a alespo¬ jedna z formulí ψ1 , ψ2 je ohodnocením h spln¥na, (4) ϕ = (ψ1 ∧ ψ2 ) a ob¥ formule ψ1 a ψ2 jsou ohodnocením h spln¥ny.
De nice 8.3.
ekneme, ºe formule je
splnitelná, pokud existuje ohodnocení, které
ji spl¬uje.
spor. Formule, která je spln¥na kaºdým ohodnotautologie. Formule ψ1 a ψ2 jsou ekvivalentní (zna£íme ≡), pokud ohodnocení h platí, ºe h spl«uje ψ1 , práv¥ kdyº spl¬uje ψ2 .
Nesplnitelná formule se nazývá cením se nazývá pro kaºdé
22
T
PÁN HOLUB Je známo, ºe booleovské formule mají následující vlastnosti:
Komutativita:
ψ1 ∨ ψ2 ≡ ψ2 ∨ ψ1 , ψ1 ∧ ψ2 ≡ ψ2 ∧ ψ1 ,
asociativita: ((ψ1 ∨ ψ2 ) ∨ ψ3 ) ≡ (ψ1 ∨ (ψ2 ∨ ψ3 )), ((ψ1 ∧ ψ2 ) ∧ ψ3 ) ≡ (ψ1 ∧ (ψ2 ∧ ψ3 )), zákon
vylou£ení t°etího
(neboli zákon
negace negace):
¬¬ψ ≡ ψ,
idempotence: ϕ ∨ ϕ ≡ ϕ, ϕ ∧ ϕ ≡ ϕ, distributivita:
((ψ1 ∨ ψ2 ) ∧ ψ3 ) ≡ ((ψ1 ∧ ψ3 ) ∨ (ψ2 ∧ ψ3 )), ((ψ1 ∧ ψ2 ) ∨ ψ3 ) ≡ ((ψ1 ∨ ψ3 ) ∧ (ψ2 ∨ ψ3 )) a
De Morganova pravidla: ¬ψ1 ∨ ¬ψ2 ≡ ¬(ψ1 ∧ ψ2 ), ¬ψ1 ∧ ¬ψ2 ≡ ¬(ψ1 ∨ ψ2 ).
Libovolnou disjunkci literál· nazýváme klausule. ekneme, ºe ϕ je v konjuktivní normální form¥, pokud je konjunkcí klausulí. ekneme, ºe ϕ je v disjunktivní normální form¥, pokud je disjunkcí formulí, z nichº kaºdá je konjunkcí literál·.
De nice 8.4. Kaºdé zobrazení f : {0, 1}n → {0, 1} nazveme booleovskou funkcí. De nice 8.5. Kaºdá booleovská formule ϕ, de nuje booleovskou funkci fϕ : {0, 1}n → {0, 1},
kde
kdyº je
ϕ
n
je po£et prom¥nných obsaºených ve
spln¥na ohodnocením
ϕ
a
fϕ (a1 , a2 , . . . , an ) = 1,
práv¥
h : xi 7→ ai .
Tvrzení 8.6.
Ke kaºdé booleovské funkci f existuje booleovská formule ϕ taková,
D·kaz.
H+
ºe f = fϕ .
Nech´
je mnoºina takových ohodnocení prom¥nných
{x1 , . . . , xn },
ºe
f (h(x1 ), . . . , h(xn )) = 1. K danému ohodnocení
h
de nujeme formuli
ψh =
n ^
lh,i ,
i=1 kde
( lh,i = Formuli
ϕ
xi , ¬xi ,
pokud pokud
h(xi ) = 1 h(xi ) = 0.
nyní de nujme jako disjunkci
ϕ=
_
ψh .
h∈H+ P°ímo£arou úvahou je moºno ov¥°it, ºe skute£n¥
f = fϕ .
Tvrzení 8.7. Kaºdá formule ϕ je ekvivalentní n¥jaké formuli v konjuktivní normální form¥ a n¥jaké formuli v disjunktivní normální form¥.
SLOITOST PRO KRYPTOGRAFII
23
∨ ∧ ∧ x1
¬
∨ x2
x3
Obrázek 2. Booleovský obvod odpovídající formuli
(x1 ∧ x2 ) ∨ ((x2 ∨ x3 ) ∧ ¬x3 ).
D·kaz.
Uvaºme booleovskou funkci
f
de novanou formulí
ϕ.
Konstrukcí popsanou
v p°edchozí v¥t¥ dostaneme formuli v disjunktivní normální form¥, která je s
ϕ
ekvivalentní. Pro získání konjunktivní normální formy formule
ϕ
vezm¥me disjunktivní nor-
¬ϕ
mální formu formule
¬ϕ =
m ^ n _ ( yi,j ), j=1 i=1
kde
yi,j
jsou literály. Pouºitím De Morganových pravidel a pravidla negace negace
dostaneme konjunktivní normální formu formule
ϕ = ¬(
m _
(
n ^
yi,j )) =
j=1 i=1
m ^
(¬(
j=1
n ^
ϕ: m _ n ^ ( (¬yi,j )).
yi,j )) =
i=1
j=1 i=1
Cyklus
G(V, E) je posloupnost vrchol· (v0 , . . . , vn ), n ≥ 1, (vi , v(i+1)mod n ) ∈ E . Acyklický graf je graf, který neobsahuje cyklus.
v orientovaném grafu
takových, ºe
De nice 8.8. {0, 1}
G = (V, E), {x1 , . . . , xn }∪{∨, ∧, ¬}∪
Booleovský obvod je kon¥£ný orientovaný acyklický graf
ve kterém je kaºdý vrchol ozna£en jedním prvkem mnoºiny a platí:
xi a 0, 1 jsou zdrojové ¬ má práv¥ jednu vstupní hranu ∨ nebo ∧ má práv¥ dv¥ vstupní hrany
(1) Vrcholy typu (2) Vrchol typu (3) Vrchol typu
De nice 8.9.
Vrchol v booleovském obvodu má p°i ohodnocení
h
hodnotu, která
je dána induktivn¥ pomocí jeho vstupních vrchol· a pomocí jeho typu.
De nice 8.10. f (a1 , . . . , an )
Vrchol
v
f : {0, 1}n → {0, 1}, ohodnocení h : xi 7→ ai .
po£ítá booleovskou funkcí
je dáno hodnotou vrchol·
v
p°i
kde
Obvykle budeme p°edpokládat, ºe uvaºovaný booleovský obvod má práv¥ jeden výstupní vrchol (vrchol z n¥hoº nevede hrana). Tento vrchol máme na mysli, pokud mluvíme o funkci po£ítané p°íslu²ným obvodem. Srovnáním De nice 8.1 a De nice 8.8 vidíme, ºe booleovský obvod je jiným vyjád°ením booleovské formule, a naopak.
De nice 8.11.
Velikostí booleovské formule rozumíme celkový po£et výskyt· ∨, ∧ ¬ ve formuli. Velikostí booleovského obvodu rozumíme po£et jeho vrchol· typu ∨, ∧ nebo ¬. nebo
Booleovský obvod na Obrázku 2 má tedy velikost 5, stejn¥ jako formule, které odpovídá.
24
T
PÁN HOLUB
Tvrzení 8.12.
Kaºdou booleovskou funkci f {0, 1}n → {0, 1} lze vypo£ítat booleovským obvodem velikosti nejvý²e 2n−1 n + n.
D·kaz.
Pouºijeme obvod odpovídající formuli po£ítající funkci
f , která je bu¤ v dis-
junktivní normální form¥, nebo konjunktivní normální form¥ (viz Tvrzení 8.7). Pokud je
|{x | f (x) = 1}| ≤ |{x | f (x) = 0}|,
pouºijeme disjunktivní normální formu,
jinak konjunktnivní. Uvaºme nap°. druhý p°ípad. Konjunktivní normální forma je konjunkcí nejvý²e
2n−1
2n−1 − 1 symbol·m ∧. Kaºdá klausule má p°esn¥ n n−1 nejvý²e 2 (n − 1) symbol· ∨. Na v²echny výskyty jedné
klausulí, coº odpovídá
literál·, tedy celkem
negované prom¥nné sta£í jediná negace. Dostáváme obvod velikosti nejvý²e
2n−1 − 1 + 2n−1 (n − 1) + n = 2n−1 n + n. 9. Redukce a úplnost
Turing·v stroj s orákulem A, kde A je n¥jaký jazyk, je vícepáskový Turingový M A , s jednou zvlá²tní dotazovací páskou a t°emi zvlá²tními stavy dotaz, ano a ne. Pokud se b¥hem výpo£tu dostane stroj do stavu dotaz, spo£ívá dal²í krok pouze v p°echodu do stavu ano nebo ne, podle toho, zda slovo napsané na dotazovací pásce leºí, nebo neleºí v A. A Stroj M tedy rozhoduje jazyk A v jednom kroku (je-li vstup na dokazovací pásce). M·ºeme to chápat jako existenci podprogramu rozhodujícího A, jehoº výpo£et se do náro£nosti M nezapo£ítává (zapo£ítává se jen jeho spu²t¥ní, jako jeden krok). To je podobné nap°. rozhodnutí, ºe násobení budeme chápat v RAM jako jedinou operaci. V tomto p°ípad¥ ov²em m·ºe být A podle de nice libovolné, i stroj, zna£íme ho
nerekurzivní. Stroje s orákulem se hodí pro zkoumání relativní obtíºnosti problém·, argument·m pouºívajícím orákula se proto °íká relativizace . Náro£nost stroje rozhoduje
B,
odpovídá na otázku, jak sloºité je rozhodnout
nároky na rozhodování jsme obtíºnost
B
A.
Je-li pro
MA
redukovali na obtíºnost
rozhodování
A.
na jazyk
A,
pí²eme
B ≤T A,
který
pokud zanedbáme
snadné, m·ºeme °íct, ºe
To vede k následující de nici.
De nice 9.1 (Turingova (Cookova) redukce). redukovatelný
B
B,
M A,
ekneme, ºe jazyk
pokud existuje
M A,
B
je
turingovsky B
který rozhoduje
v polynomiálním £ase. Tato de nice chápe snadnost z p°edchozí diskuse jako rozhodnutelnost v polynomiálním £ase. Bylo by samoz°ejm¥ moºné uvaºovat i jiné moºnosti. Tvrzení
B ≤T A
chápeme tak, ºe
B
je leh£í (p°esn¥ji, není o mnoho t¥º²í) neº
Jiná, p°ísn¥j²í forma redukce dovoluje stroji
M
A.
pouºít sluºby orákula jen jed-
nou, a to na konci výpo£tu tak, ºe odpov¥¤ orákula je sou£asn¥ odpov¥dí stroje
M.
V takovém p°ípad¥ obvykle nemluvíme o orákulu, ale °íkáme, ºe stroj
kuje instanci problému
B
názornost nazývá obvykle
De nice 9.2
na instanci problému
R).
A
M
redu-
(stroj se v takovém p°ípad¥ pro
Dostáváme tak následující de nici.
(Karpova (Levinova, many-one) redukce)
karpovsky redukovatelný na jazyk A, pí²eme B ≤P A, stroj R takový, ºe R(x) ∈ A, práv¥ kdyº x ∈ B .
.
ekneme, ºe jazyk
B
je
pokud existuje polynomiální
Karpova redukce op¥t po£ítá s polynomiálním £asem nutným pro redukci, p°esn¥ji bychom tedy m¥li mluvit o
polynomiální Karpov¥ redukci.
Název many-one
redukce odkazuje na fakt, ºe narozdíl od Turingovy redukce m·ºe stroj
R
b¥hem
mnoha svých krok· pouºít orákulum jen jednou. Karpova redukce byla de nována
SLOITOST PRO KRYPTOGRAFII v souvislosti s t°ídou
NP
25
a má zjevn¥ smysl jen pro problémy, které jsou t¥º²í neº
polynomiální. Redukovat karpovsky nap°. n¥jaký problém z
NL
nebo z
P
není za-
jímavé, protoºe ho m·ºeme, namísto redukce, v polynomiálním £ase rovnou vy°e²it. Proto se £asto pouºívá je²t¥ p°ísn¥j²í redukce.
De nice 9.3
telný
.
(Log-space redukce)
na jazyk
A,
ekneme, ºe jazyk
B ≤L A, pokud existuje R R(x) ∈ A, práv¥ kdyº x ∈ B .
pí²eme
náro£ností takový, ºe
B
je
log-space redukova-
s logaritmickou prostorovou
Následující v¥ta potvrzuje, ºe je napln¥na intuice, se kterou jsme redukce de -
B
novali: je-li
polynomiální redukce jazyka
Tvrzení 9.4
pak B ∈ P.
A, není B t¥º²í neº A. Há£ek v této úvaze by mohl B bude skryta práv¥ v redukci, jako nap°. v p°ípad¥ z L.
redukovatelné na
spo£ívat v tom, ºe obtíºnost
(P je uzav°ena na Karpovu redukci.)
.
Pokud B ≤P A, kde A ∈ P,
D·kaz.
Nech´ R ∈ P je Karpova redukce jazyka B na A ∈ P, náro£nosti p(n). M je polynomiální algoritmus sloºitosti q(n) rozhodující L2 . Pak sloºení T = M ◦ R rozhoduje B . Sloºitost T je nejvý²e p(n) + q(p(n)), protoºe délka R(x) je nejvý²e p(|x|). Tím je d·kaz u konce, nebo´ p(n) + q(p(n)) je polynom.
Nech´
Otázka log-space uzav°enosti
L
v následující v¥t¥ je komplikovan¥j²í tím, ºe
výstup stroje se nezapo£ítává do prostorové náro£nosti, p°i£emº m·ºe být podstatn¥ v¥t²í neº
log(n).
Prostorová náro£nost prostého sloºení, tedy v·bec nemusí být
logaritmická.
Tvrzení 9.5 pak B ∈ L.
.
(L je uzav°ena na log-space redukci.)
Pokud B ≤L A, kde A ∈ L,
D·kaz. Nech´ R ∈ L je log-space redukce jazyka B na A ∈ L a nech´ M rozhoduje A v logaritmickém prostoru. Pak B je rozhodován následujícím algoritmem T s logaritmickou prostorovou náro£ností. Algoritmus T simuluje v na jedné pásce b¥h algoritmu M . Kdykoli M chce p°e£íst i-tý symbol svého vstupu simuluje T na druhé pásce b¥h stroje R. Namísto psaní výstupu v²ak pouze na t°etí pásce po£ítá kolikátý symbol výstupu má být vypsán. Po dosaºení i-tého symbolu ho p°edá stroji M jako i-tý symbol vstupu. Na prvních dvou páskách je prostorová náro£nost logaritmická podle p°edpokladu. Zbývá uváºit náro£nost po£ítadla. Po£ítadlo musí obsáhnout nejvý²e po£et
R. Ten v²ak pracuje v logaritmickém prostoru, a po£et jeho krok· je O(nk ) (podle obvyklé diskuse o po£tu snímk·). To znamená, ºe po£ítadlu prostor O(log(n)).
krok· stroje tedy v sta£í
Pojem turingovské redukce byl de nován Cookem v roce 1971 a pojem karpovské redukce Karpem v roce 1972. V obou p°ípadech byla motivací redukce v²ech problém· z
NP
na jeden z nich. To vede k de nici
úplných
a
t¥ºkých
jazyk· dané
sloºitostní t°ídy vzhledem k dané redukci.
De nice 9.6. B ≤r A
Nech´
r ∈ {T, L, P }. ekneme, ºe jazyk A je ≤r -t¥ºký pro C , pokud B ∈ C . Je-li navíc A ∈ C , nazývá se ≤r -úplný pro C .
pro kaºdý jazyk
Obvykle se charakteristika t¥ºkých a úplných jazyk· zkracuje. Není-li °e£eno
NP-úplným (resp. NP-t¥ºkým) jazyk, který je ≤P -úplný NP. V p°ípad¥ t°ídy P nebo NL je uvaºovanou redukcí ≤L .
jinak, nazýváme
≤P -t¥ºký)
pro
(resp.
10. Alternativní charakteristika t°ídy NP
R je polynomiáln¥ omezená, (x, y) ∈ R platí |y| ≤ p(|x|).
ekneme, ºe relace kový, ºe pro v²echna
pokud existuje polynom
p
ta-
26
T
PÁN HOLUB
Tvrzení 10.1. Jazyk L leºí v NP práv¥ kdyº existuje polynomiáln¥ omezená relace RL ∈ P taková, ºe x ∈ L, práv¥ kdyº (x, y) ∈ RL pro alespo¬ jedno y . Relaci
je
sv¥dek
RL
nazýváme
pro
x.
sv¥deckou relací
jazyka
L
a je-li
(x, y) ∈ RL ,
°íkáme, ºe
y
P°íklad 10.2. • L = {n | n je sloºené £íslo} RL = {(a, b) | 2 ≤ b < a, b|a} • RSAT = {(ϕ, k) | k spl¬uje ϕ} • RCIRCSAT = {(C, σ) | C(σ) = 1}. D·kaz.
Chceme ukázat, ºe charakterizace
NP
pomocí sv¥deckých relací je ekviva-
lentní de nici pomocí nedeterministických stroj·. Nech´ je
L rozhodován nedeterministickým strojem M . Pak jako sv¥deckou relaci
m·ºeme zvolit
RL = {(x, y) | x ∈ L, y Pokud je naopak
RL
je vektor voleb p°ijímajícího výpo£tu
sv¥decká relace pro
nedeterministický stroj rozhodující
• •
zvol sv¥dka
y
zjisti pomocí
L
L
x
strojem
rozhodovaná strojem
zda
sestrojíme
takto:
(p°íslu²né délky dané polynomiální omezeností
T,
T,
M }.
RL ),
(x, y) ∈ RL .
Nedeterministický stroj
T
v p°edchozím d·kazu se vyzna£uje tím, ºe ve²kerý
nedeterminismus je koncentrován na za£átek výpo£tu, do volby sv¥dka, a poté je výpo£et deterministický. M·ºeme to také chápat tak, ºe stroj si na po£átku nageneruje vektor voleb, kterým se potom (deterministicky) °ídí p°i rozhodování jakou pouºít instrukci. 11. NP-úplnost T°ída
NP
obsahuje stovky úplných problém·, v£etn¥ mnoha d·leºitých a p°iro-
zených obtíºných problém· (nap°. problém obchodního cestujícího, barvení grafu, hamiltonovská cesta v grafu).
≤P je tranzitivní. D·kaz je snadný a podobný P na ≤P . Z toho plyne, ºe pokud n¥jaký NP-úplný problém karpovsky redukujeme na problém B , dokáºeme tím, ºe i B je NP-úplný. To je obvyklý postup p°i dokazování NP-úplnosti. První a nejd·leºit¥j²í problém, stojící V²imn¥me si nejprve, ºe relace
jako d·kaz uzav°enosti
v £ele v²ech podobných redukcí je problém splnitelnosti booleovských formulí nebo obvod·. Ten tak hraje pro
NP-úplnost
podobnou roli jako HaltingProblem pro
nerozhodnutelnost. Problém SAT poºaduje rozhodnout, zda je daná booleovská formule rozhodnutelná. Tedy
SAT
= {ϕ | ϕ
je splnitelná booleovská formule}.
V¥ta 11.1 (Cookova-Levinova).
SAT
D·kaz.
∈ NP.
Ukaºme nejprve, ºe SAT
je NP-úplný. Nedeterministický algoritmus rozhodující
SAT pracuje následovn¥:
• •
Zvol ohodnocení Pokud je
ϕ
h(n)
ohodnocením
h(n)
spln¥na, p°ijmi; jinak odmítni.
Spo£ítat hodnotu formule s daným ohodnocením je jist¥ moºné v polynomiálním £ase. Uvedený algoritmus tedy pracuje v polynomiálním nedeterministickém £ase a p°ijímá práv¥ splnitelné formule.
SLOITOST PRO KRYPTOGRAFII
27
A ∈ NP a nech´ M ∈ NTM rozhoduje A. Popí²eme, jak pro vstup ϕ(x), která bude splnitelná, práv¥ kdyº bude existovat výpo£et stroje M , p°ijímající x. Budeme p°edpokládat, ºe M je jednopáskový stroj s jednostrann¥ nekone£nou Nech´ nyní
x
utvo°it formuli
páskou, tedy s polí£ky o£íslovanými p°irozenými £ísly. Takový p°edpoklad jist¥
M pracuje s abecedou Σ = {σ1 , σ2 , . . . , σ` }, v£etn¥ {q1 , q2 , . . . , qr }, p°i£emº q1 je po£áte£ní stav a qr stav p°ijímající. Doba b¥hu stroje M nech´ je omezena polynomem p. Na vstupu x tedy stroj vykoná nejvý²e τ := p(|x|) krok· a nav²tíví nejvý²e prvních τ polí£ek. P°edpokládejme dále, ºe pro kaºdý okamºitý popis existuje nejvý²e c instrukcí. Program
není na újmu obecnosti. Nech´
σ 1 = ,
a mnoºinou stav·
stroje upravíme zopakováním n¥kterých instrukcí tak, aby pro kaºdý okamºitý popis
c. Po zastavení stroje jsou v²echny následující snímky, aº τ , rovny tomu, ve kterém se stroj zastavil. Jinak °e£eno, pro kaºdý okamºitý popis s koncovým stavem de nujeme triviální instrukci (qr , σ, qr , σ, _). Formule ϕ(x) bude obsahovat následující prom¥nné: existovalo instrukcí p°esn¥
do £asu
i {Ps,t | 1 ≤ i ≤ `, 1 ≤ s, t ≤ τ },
{Qit | 1 ≤ i ≤ r, 1 ≤ t ≤ τ }, {Ss,t | 1 ≤ s, t ≤ τ }, {Dti | 1 ≤ i ≤ c, 1 ≤ t ≤ τ }. Význam prom¥nných p°i ohodnocení odpovídajícím p°ijímajícímu výpo£tu je tento
i = 1 práv¥ kdyº polí£ko £íslo s obsahuje v £ase t symbol σ1 , Ps,t Qit = 1 práv¥ kdyº je stroj v £ase t ve stavu qi , Ss,t = 1 práv¥ kdyº v £ase t £te hlava polí£ko s, Dti = 1 práv¥ kdyº stroj v £ase t zvolil i-tou z moºných instrukcí. Formule ϕ(x) má tvar ϕ(x) = ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕ7 ,
• • • •
ϕi mají následující podobu a význam. ϕ1 vyjad°uje, ºe v kaºdém okamºiku je £teno práv¥ jedno polí£ko: ! τ τ τ ^ _ ^ ϕ1 = Ss,t ∧ (¬Si,t ∨ ¬Sj,t ) ;
kde
t=1
ϕ2
s=1
i, j = 1 i<j
vyjad°uje, ºe v kaºdém okamºiku je stroj v práv¥ jednom stavu:
ϕ2 =
τ r ^ _ Qit
t=1
ϕ3
!
r ^
∧
i=1
i, j = 1 i<j
¬Qit ∨ ¬Qjt ;
vyjad°uje, ºe v kaºdém okamºiku obsahuje kaºdé polí£ko práv¥ jeden symbol:
ϕ3 =
τ ^ s, t = 1
ϕ4
` _
! ` Ps,t
k=1
` ^
∧
i, j = 1 i<j
vyjad°uje, ºe po£áte£ní situace je ve správném tvaru:
ϕ4 = Q11 ∧ S1,1 ∧
n ^ i=1
kde
j i ; ¬Ps,t ∨ ¬Ps,t
x = σk1 σk2 · · · σkn .
ki Pi,1 ∧
τ ^ i=n+1
1 Pi,1 ,
28
T
PÁN HOLUB
ϕ5
vyjad°uje, ºe výpo£et obsahuje p°ijímající stav:
τ _
Qrt .
t=1 Zbývá zaru£it korektnost p°echod·.
ϕ6
vyjad°uje, ºe polí£ko, které není £teno, se nem¥ní:
τ^ −1
¬Ss,t ⇒
=
s,t=1
ϕ7
` ^
! i i Ps,t ⇔ Ps,t+1
i=1
t, (qi , σj ) a volbu d de nujeme formuli 0 j j0 ψs,t,i,j,d = Qit ∧ Ss,t ∧ Ps,t ∧ Dtd ⇒ Qit+1 ∧ Ss0 ,t+1 ∧ Ps,t+1 ,
vyjad°uje, ºe zvolená instrukce byla správn¥ provedena. Pro £as
polí£ko
s,
okamºitý popis
(qi , σj , qi0 , σj 0 , m) je d-tá instrukce s okamºitým popisem (qi , σj ) 1, s, s + 1} v souladu s pohybem m. Formule ϕ7 má nyní tvar ^ ϕ7 = ψs,t,i,j,d .
kde
a
s0 ∈ {s −
1 ≤ s, t < τ 1≤i≤r 1≤j≤` 1≤d≤c Je z°ejmé, ºe uvedenou formuli lze zkonstruovat v £ase
O(p(n)2 )
a z konstrukce
plyne, ºe má poºadovanou vlastnost. Z d·vodu p°ehlednosti jsme pouºili i jiné spojky neº
∧, ∨
a
¬.
Pro úplnost je tedy dode nujme jako zkratky:
ψ1 ⇒ ψ2 :≡ ¬ψ1 ∨ ψ2 ψ1 ⇔ ψ2 :≡ (¬ψ1 ∨ ψ2 ) ∧ (¬ψ2 ∨ ψ1 ) Vzhledem k tomu, ºe lze snadno zkonstruovat formuli odpovídající danému booleovskému obvodu, plyne jako okamºitý d·sledek
NP-úplnost
problému splnitelnosti
booleovských obvod·, ozna£ovaný jako CIRCSAT.
D·sledek 11.2.
CIRCSAT
je NP-úplný.
Je jasné, ºe SAT obsahuje mnoho formulí, jejichº splnitelnost je snadné rozhodnout, nap°. formule v disjunktivní normální form¥.
NP
úplnost tedy plyne z
n¥jaké podmnoºiny formulí, které jsou t¥ºké. Ukazuje se, ºe sta£í omezit na formule s pom¥rn¥ jednoduchým tvarem. Ozna£me 3SAT mnoºinu booleovských formulí v konjunktivní normální form¥, ve kterých navíc kaºdá klausule obsahuje nejvý²e t°i literály. Vstup si m·ºeme p°edstavit jako seznam nejvý²e trojprvkových podmnoºin prom¥nných. Nap°.
{x1 , x3 }, {x2 , ¬x4 , ¬x5 }, {¬x1 , x2 } representuje formuli
(x1 ∨ x3 ) ∧ (x2 ∨ ¬x4 ∨ ¬x5 ) ∧ (¬x1 ∨ x2 ).
Tvrzení 11.3. D·kaz.
je NP-úplný.
Redukujeme CIRCSAT na 3SAT. K danému obvodu
m¥nnými muli
3SAT
ϕC ,
{x1 , x2 , . . . , xn } a nevstupními vrcholy V
C
se vstupními pro-
zkonstruujeme booleovskou for-
jejíº prom¥nné budou
{x1 , x2 , . . . , xn } ∪ {xv | v ∈ V }. Pro kaºdý vrchol form¥ následovn¥.
v
okruhu
C
zkonstruujeme formuli
ϕv
v konjunktivní normální
SLOITOST PRO KRYPTOGRAFII Je-li vrchol
v
typu
¬
u
se vstupním vrcholem
29 poloºme
ϕv = (xv ∨ xu ) ∧ (¬xv ∨ ¬xu ). Platí, ºe ohodnocení Pro
v
typu
∧
h : {xu , xv } → {0, 1} spl¬uje ϕv práv¥ u a w poloºíme
kdyº
h(xv ) 6= h(¬xu ).
se vstupními vrcholy
ϕv = (xu ∨ ¬xv ) ∧ (xw ∨ ¬xv ) ∧ (¬xu ∨ ¬xw ∨ xv ) . h : {xu , xv , xw } → {0, 1}
Op¥t platí, ºe ohodnocení
spl¬uje
ϕv
práv¥ kdyº
h(xv ) =
h(xu ∧ xw ). Nakonec pro
v
∨
typu
se vstupními vrcholy
u
a
w
poloºíme
ϕv = (¬xu ∨ xv ) ∧ (¬xw ∨ xv ) ∧ (xu ∨ xw ∨ ¬xv ), takºe
h(ϕv ) = 1,
práv¥ kdyº
Ozna£me výstupní vrchol
h(xv ) = h(xu ∨ xw ). C symbolem vF . Nyní jiº ^ ϕC = ( ϕ v ) ∧ x vF .
m·ºeme de novat
v∈V Redukce je z°ejm¥ polynomiální. Tvrdíme, ºe
C
je splnitelný, práv¥ kdyº
ϕC
je
splnitelná. Nech´ je
h
ohodnocení, které spl¬uje
nocení vrchol· obvodu
C
h
h(xvF ) = 1.
Pak jist¥
h(v) = h(xv )
Konstrukce formule zaru£uje, ºe okruh je ohodnocením
ϕC .
dané ohodnocením
h
Uvaºujme ohod-
jeho vstupních vrchol· vrcholy.
pro kaºdé
v ∈V.
Tedy i
h(vF ) = 1
a
spln¥n.
h ohodnocení vstupních vrchol· obvodu C takové, ºe h(vF ) = 1. xv , v ∈ V p°edpisem h(xv ) = h(v). Z konstrukce formule ohodnocení h spl¬uje.
Nech´ je naopak
h
Roz²i°me
ϕC
na prom¥nné
plyne, ºe ji
Dal²í, je²t¥ men²í podmnoºinou SAT, která je v²ak stále
NP-úplná je NAESAT
Not All Equal). Je to podmnoºina 3SAT obsahující pouze formule, pro n¥º exis-
(
tuje ohodnocení takové, ºe pro ºádnou klausuli nejsou hodnoty v²ech literál· stejné. Splnitelnost poºaduje, aby hodnota alespo¬ jednoho literálu v kaºdé klausuli byla 1. NAESAT navíc poºaduje, aby hodnota alespo¬ jednoho literálu byla 0. Je-li
h
¯ ozna£íme opa£né X , pak h ¯ platí h(x) = 1 − h(x). Formuli ϕ ∈ NAESAT ¯ ji pro ni existuje ohodnocení h takové, ºe h i h
n¥jaké ohodnocení prom¥nných z mnoºiny
ohodnocení, tj. takové, pro n¥º m·ºeme charakterizovat tak, ºe spl¬uje.
Tvrzení 11.4. D·kaz.
NAESAT
je NP-úplný.
Provedeme redukci CIRCSAT na NAESAT mírnou úpravou redukce na
3SAT. Nadále budeme pouºívat zna£ení z p°edchozího d·kazu. Nech´
ϕ0v
vznikne z
ϕv
p°idáním nové prom¥nné
z
do v²ech klausulí, které obsa-
hují mén¥ neº t°i literály. Ukáºeme, ºe
ϕ0C = (
^
ϕ0v ) ∧ (xvF ∨ z)
v∈V leºí v NAESAT, práv¥ kdyº
C
je splnitelný okruh.
¯ spl¬uje ϕ0 . Díky symetrii h a h ¯ m·ºeme p°edpokládat h(z) = 0. hah C Pak h zjevn¥ spl¬uje ϕC , a tedy C ∈ CIRCSAT. Nech´ naopak C ∈ CIRCSAT a h spl¬uje ϕC . Pak h roz²í°ené o h(z) = 0 spl¬uje 0 ¯ (roz²í°ené o h(z) ¯ i ϕC . Ohodnocení h = 1) jist¥ spl¬uje klausule obsahující z . Zbývá ukázat, ºe spl¬uje i klausule, které z neobsahují. Nech´ v je typu ∧ se vstupy u a w . Ohodnocení h spl¬uje (u ∨ ¬v) i (w ∨ ¬v), ¯ spl¬uje (¬u ∨ ¬w ∨ v). odkud snadno odvodíme, ºe h Nech´ je nyní v typu ∨ se vstupy u a w . Jelikoº h spl¬uje (¬u ∨ v) i (¬w ∨ v), ¯ klausuli (u ∨ w ∨ ¬v). spl¬uje h Nech´ tedy
30
T
PÁN HOLUB Poslední
NP-úplný problém, který uvádíme, je jeden z mnoha NP-úplných pro-
blém· z teorie graf·:
3Coloring
= {G |
graf
G
je obarvitelný t°emi barvami}.
G = (V, E) t°emi barvami (u, v) ∈ E , pak γ(u) 6= γ(v).
P°ipome¬me, ºe obarvení grafu
{0, 1, 2}
takové, ºe pokud
Tvrzení 11.5. D·kaz.
3Coloring
je zobrazení
γ : V →
je NP-úplný.
Ukáºeme redukci NAESAT na 3Coloring. M¥jme formuli
ϕ,
která je v
konjunktivní normální form¥ a kaºdá klausule obsahuje dva nebo t°i literály. (Pokud n¥jaká klausule obsahuje jen jeden literál, formule jist¥ v NAESATneleºí.) Tuto vlastnost lze zkontrolovat v polynomiálním £ase. (A pokud vstup nemá poºadovaný tvar, sta£í ho p°evést na n¥jaký nep°ijatelný vstup 3Coloring.) Mnoºina prom¥nných budiº klausulí se t°emi literály a
m ^
ϕ=
`
X = {x1 , . . . , xn }
a formule
ϕ
nech´ je konjunkcí
m
klausulí se dv¥ma literály, tedy tvaru
(ck,1 ∨ ck,2 ∨ ck,3 ) ∧
k=1
m+` ^
(ck,1 ∨ ck,2 ),
k=m+1
ck,i ∈ X ± = {x1 , . . . , xn , ¬x1 , . . . , ¬xn }. ± Vrcholy V konstruovaného grafu budou sestávat z prvk· mnoºiny X , uspo°ádaných dvojic (k, i), k = 1, . . . , m, i = 1, 2, 3, a jednoho speciálního vrcholu b. Celkem tedy |V | = 3m + 2n + 1. Mnoºina hran E je následující: (1) (xi , ¬xi ) ∈ E pro v²echna i = 1, . . . , n; (2) (xi , b) ∈ E , (¬xi , b) ∈ E , pro v²echna i = 1, . . . , n; (3) ((k, i), (k, j)) ∈ E pro v²echna k = 1, 2, . . . , m a i, j = 1, 2, 3, i 6= j ; ± (4) ((k, i), y) ∈ E pro v²echna (k, i) a y ∈ X taková, ºe y = ck,i ; (5) (ck,1 , ck,2 ) pro v²echna k = m + 1, m + 2, . . . , m + `. Následující obrázek ilustruje £ást grafu odpovídající k -té klausuli (¬x1 ∨ x2 ∨ x4 ) a klausuli (x3 ∨ ¬x4 ).
kde
b •
• x1
• ¬x1
• x2
• ¬x2
• x3
(k,2)
•
•
•
(k,1)
(k,3)
• ¬x3
• x4
• ¬x4
SLOITOST PRO KRYPTOGRAFII
31
G = (V, E) dokon£en. Je z°ejmé, ºe redukce je polynomiální. G ∈ 3Coloring, práv¥ kdyº ϕ ∈ NAESAT. Nech´ je nejprve G ∈ 3Coloring a γ : V → {0, 1, 2} je jeho obarvení t°emi barvami. M·ºeme p°edpokládat γ(b) = 2. Odtud plyne, díky hranám uvedeným pod body (1) a (2), ºe γ(x) ∈ {0, 1} a γ(x) 6= γ(¬x) pro v²echna x ∈ X . M·ºeme tedy de novat ohodnocení h mnoºiny X p°edpisem h(x) = γ(x). Ukáºeme, ºe h spl¬uje ϕ. Zvolme k ∈ {1, . . . , m}. Vzhledem k tomu, ºe vrcholy (k, i), i = 1, 2, 3, jsou spojeny hranami, existuje i0 takové, ºe γ(k, i0 ) = 0. Kv·li hranám popsaným v bod¥ (4) je γ(ck,i0 ) = 1, a tudíº také h(ck,i0 ) = 1. Pro k = m + 1, m + 2, . . . , m + ` platí díky hran¥ z bodu (5), ºe h(ck,i ) = 1 pro práv¥ jedno i = 1, 2. Ohodnocení h tedy ¯ , a proto ϕ ∈ NAESAT. spl¬uje v²echny klausule. Stejná úvaha je moºná i pro h ¯ jsou opa£ná ohodnocení, která spl¬ují ϕ. Nech´ je nyní ϕ ∈ NAESAT a h a h ± Vrchol b a vrcholy X obarvíme takto Tím je popis grafu
Ukáºeme, ºe
• γ(b) = 2; • γ(ck,i ) = h(ck,i ), Uvaºujme nyní klausuli
pro v²echna
ck,i ∈ X ± .
(ck,1 ∨ ck,2 ∨ ck,3 ). Vzhledem k tomu, ºe h je ohodnocení i1 , i2 ∈ {1, 2, 3} taková, ºe h(ck,i1 ) 6= h(ck,i2 ).
podle podmínek NAESAT, existují De nujme
¯ k,i ); • γ((k, i1 )) = h(c 1 ¯ k,i ); • γ((k, i2 )) = h(c 2 • γ((k, i3 )) = 2, kde {i1 , i2 , i3 } = {1, 2, 3}. P°ímo£a°e ov¥°íme, ºe
γ
je obarvení
G.
Zmi¬me na záv¥r bez d·kaz· (které nejsou t¥ºké) dv¥ varianty problému SAT, které leºí v
P. Klausule se nazývá Hornova, pokud obsahuje nejvý²e jeden pozitivní
literál. De nujme
HornSAT
Tvrzení 11.6.
= {ϕ | ϕ
HornSAT
je splnitelná konjunkce Hornových klauzulí}.
∈ P.
Sníºíme-li po£et literál· v klausuli ze t°í na dva, stane se problém °e²itelný v polynomiálním £ase.
2SAT
= {ϕ | ϕ ∈ CNF
Tvrzení 11.7.
2SAT
a kaºdá klausule obsahuje nejvý²e dva literály}.
∈ P. 12. Pravd¥podobnostní odhady
D·leºitým aspektem pravd¥podobnostních algoritm·, kterými se budeme zabývat dále, je moºnost opakovat stejný výpo£et vícekrát. Zatímco pro deterministický algoritmus nedává takový postup ºádný smysl, u pravd¥podobnostních algoritm· se opakováním mohou dramaticky m¥nit pravd¥podobnosti správné odpov¥di. Má-li nap°. n¥jaký polynomiální algoritmus pravd¥podobnost úsp¥chu
1/nk ,
coº bychom
intuitivn¥ povaºovali za pravd¥podobnost p°íli² malou, sta£í opakovat tento algoritmus
nk -krát
a sníºíme pravd¥podobnost neúsp¥chu na
nk 1 −→ 1− k n
k
e−n .
Polynomiáln¥ malou úsp¥²nost je tedy moºné zm¥nit na exponenciáln¥ malou neúsp¥nost, p°i£emº celková sloºitost z·stane polynomiální. Tato úvaha platí pro p°ípad, kdy úsp¥²ný b¥h algoritmu s jistotou poznáme, nap°. pokud algoritmus generuje sv¥dka pro n¥jaký jazyk v
NP.
32
T
PÁN HOLUB D·leºité jsou ale také situace, kdy správnou odpov¥¤ nepoznáme a rozhodujeme
se na základ¥ v¥t²inového výsledku. V takových p°ípadech pot°ebujeme pravd¥podobnostní odhady související se zákonem velkých £ísel: pr·m¥rná hodnota opakovaného experimentu se blíºí jeho st°ední hodnot¥. Ale jak rychle a s jakou pravd¥podobností? Na to odpovídají následující odhady. D·leºitou okolností je míra nezávislosti opakovaných experiment·:
• • •
Markovova nerovnost platí pro jakoukoli náhodnou veli£inu, ale je nejslab²í. Siln¥j²í eby²evova nerovnost platí pro
po dvou
nezávislé veli£iny.
Nejsiln¥j²í je Cherno·v odhad, který ale vyºaduje zcela nezávislé veli£iny.
Ω napravd¥podobnostním prostorem pokud je na ní de nována míra µ taková, ºe µ(Ω) = 1. Pro na²e pot°eby sta£í uvaºovat spo£etné pravd¥podobnostní prostory. ∗ Typicky bude Ω = N nebo Ω = {0, 1} . To umoº¬uje psát místo integrál· sumy. Náhodná veli£ina X je zobrazení X : Ω → R. St°ední (neboli o£ekávaná) hodnota X je X E(X) = X(ω)µ(ω). Zopakujme nejprve základní pojmy teorie pravd¥podobnosti. Mnoºinu
zveme
ω∈Ω
A
Pravd¥podobnost n¥jakého jevu
budeme zna£it
Pr [A].
Je dána mírou pod-
mnoºiny pravd¥podobnostního prostoru, pro kterou jev nastává. Vý²e jsme popsali situaci, kdy zkoumáme náhodnou veli£inu
X=
Pn
i=1
Zi .
Pro
její st°ední hodnotu platí
E(X) =
n X
E(Zi ),
i=1 a to bez ohledu na závislost £i nezávislost veli£in pravd¥podobnost, ºe se hodnota veli£iny
X
Zi .
Klí£ová otázka zní, jaká je
bude od o£ekávané hodnoty daným
zp·sobem li²it. Dokáºme první odhad.
V¥ta 12.1
(Markovova nerovnost)
notami a k > 0. Pak
.
Nech´ je X náhodná veli£ina s kladnými hod-
Pr [X ≥ k] ≤
E(X) . k
D·kaz. E(X) =
X
X(ω)µ(ω) =
ω∈Ω
≥
X
X(ω)µ(ω) +
X(ω)
X
X(ω)µ(ω) ≥ k ·
X(ω)≥k
X
X(ω)µ(ω)
X(ω)≥k
X
µ(ω) = k · Pr [X ≥ k] .
X(ω)≥k
Jak moc se náhodná veli£ina pro jednotlivé prvky pravd¥podobnostního prostoru li²í od své o£ekávané hodnoty vyjad°uje
rozptyl
neboli
variance,
de novaná
Var(X) := E((X − E(X))2 ) = E(X 2 ) − E(X)2 . Jednoduchou aplikací Markovovy nerovnosti na formuli rozptylu dostáváme druhý odhad.
V¥ta 12.2 (eby²ev·v odhad). Pr [ |X − E(X)| ≥ t ] ≤
Var(X) . t2
SLOITOST PRO KRYPTOGRAFII
33
D·kaz. Markov Var(X) . ≤ Pr [ |X − E(X)| ≥ t ] = Pr (X − E(X))2 ≥ t2 t2 Zi
je zásadní skute£nost,
ZiP po dvou nezávislé kopie náhodné veli£iny Z , dává m X = i=1 Zi odhad X Var(Z) . Pr − E(Z) ≥ ε ≤ m m ε2
eby²evova nerovnost
Pro aplikaci eby²evovy nerovnosti pro p°ípad ºe pokud jsou veli£iny
Zi
po dvou nezávislé, platí
Var
X
X Zi = Var(Zi ).
Jsou-li pro
P°íklad
12.3. Typickou zkoumanou situací je opakování experimentu s Bernoulliho
rozd¥lením se st°ední hodnotou hodnot
{0, 1}
0 ≤ p ≤ 1,
Snadno ov¥°íme, ºe
Z,
tedy náhodné veli£iny
Z
nabývající
takové, ºe
Pr [Z = 0] = 1 − p .
Pr [Z = 1] = p kopie
X=
P
E(Z) = pPa Var(Z) = p(1 − p). Jsou-li Zi m X = i=1 Zi odhad X p (1 − p) . Pr − p ≥ ε ≤ m m ε2
po dvou nezávislé
dostáváme pro
Jsou-li s£ítané veli£iny zcela nezávislé, m·ºeme odhad výrazn¥ zlep²it Chernoovým odhadem. Odhad vyuºívá fakt, ºe st°ední hodnota sou£inu nezávislých veli£in je sou£in jejich st°edních hodnot. Cherno·v odhad ukáºeme v p°esné formulaci pro sou£et náhodných veli£in se stejným Bernoulliho rozd¥lením.
V¥ta 12.4 (Cherno·v odhad). Uvaºujme nezávislé kopie náhodných veli£in Zi , i = 1, . . . , m náhodné veli£iny Z s Bernoulliho rozd¥lením a st°ední hodnotou p a poloºme m X Zi . X= i=1
Pak platí
(12.1)
(12.2)
X Pr ≥ p + ε ≤ exp (−m · D(p + ε k p)) m X Pr ≤ p − ε ≤ exp (−m · D(1 − p + ε k 1 − p)) , m
kde D(x k y) := x ln
D·kaz.
x 1−x + (1 − x) ln . y 1−y
t > 0 a libovolné k > 0 platí Pr [X ≥ k] = Pr etX ≥ etk E etX ≤ podle Markovovy nerovnosti, etk m E etZi z nezávislosti Zi , = etk (p et + 1 − p)m = p°ímým výpo£tem E(exp (tZi )). etk Pro libovolné
34
T
PÁN HOLUB
Pro
t = ln
(1 − p) (p + ε) p (1 − p − ε)
k = m (p + ε)
a
dostáváme vztah (12.1). Nerovnost (12.2) je ekvivalentní nerovnosti (12.1) pro veli£inu
Y =
Funkce
x
a
y
Pm
i=1 (1
D(x k y)
− Zi ). je
relativní entropie
Bernoulliho distribucí se st°ední hodnotou
(v²imn¥te si, ºe záleºí na po°adí, formule není symetrická). Z konkávnosti
logaritmu dostáváme
− D(x k y) = x ln
y x
+ (1 − x) ln
Relativní entropie je tedy vºdy kladná pro
x 6= y
1−y 1−x
≤ ln 1 = 0 .
(a nulová pro
x = y)
a Chernof-
f·v odhad poskytuje exponenciáln¥ rychle klesající pravd¥podobnost odchylky od o£ekávané hodnoty s rostoucímpo£tem opakování. Analýzou relativní entropie lze získat následující prakti£t¥j²í odhady, které uvá-
D(p + ε k p) ≥ 2ε2 plyne X Pr − p ≥ ε ≤ 2 exp −2 m ε2 . m
díme bez d·kazu. Z odhadu
asto se uvád¥jí multiplikativní verze Chernoova odhadu:
X δ2 Pr ≤ (1 − δ) p ≤ exp − m p · . m 2 X δ2 Pr ≥ (1 + δ) p ≤ exp − m p · . m 2+δ
13. Pravd¥podobnostní algoritmy a sloºitostní t°ídy Nedeterministický Turing·v stroj je výpo£etní model, jehoº de nice p·sobí velmi nerealisticky, protoºe p°edpokládáme, ºe v²echny v¥tve výpo£tu probíhají sou£asn¥. V reálném situaci je p°irozené p°edpokládat, ºe stroj si musí jedno z pokra£ování vybrat. Pokud stanovíme s jakou pravd¥podobností si jednotlivé de nované moºnosti vybírá, dostáváme de nici pravd¥podobnostního Turingova stroje.
De nice 13.1.
Pravd¥podobnostní Turing·v stroj je nedeterministický Turing·v
stroj spolu s funkcí
(q, a) ∈ Q × A
P : (Q × A × Q × A × M ) → [0, 1]
takovou, ºe pro kaºdé
platí
X
P (q, a, q 0 , a0 , m) = 1
(q 0 ,a0 ,m0 )∈Q×A×M kde
Q je mnoºina stav·, A je mnoºina symbol· a M = (←, →, −) mnoºina pohyb·.
T°ídu pravd¥podobnostních Turingových stroj· budeme zna£it
P
PTM). Funkce (q, a) in-
ur£uje s jakou pravd¥podobností pouºije stroj v okamºitém stavu
(q, a, q 0 , a0 , m0 ). Funkce je de novaná pro v²echny moºné instrukce. P°ípad P (q, a, q 0 , a0 , m) = 0 odpovídá situaci, v níº se daná instrukce v programu nevyskystrukci
tuje (je pouºita s nulovou pravd¥podobností). asová i prostorová náro£nost pravd¥podobnostních stroj· se de nuje podobn¥ jako u stroj· nedeterministických, tedy spot°ebou v nejnáro£n¥j²ím p°ípad¥. Pravd¥podobnostní stroje hrají v kryptogra i klí£ovou úlohu, protoºe bezpe£nost systému je ohroºena nejen tehdy, pokud existuje útok, který je úsp¥²ný vºdy, ale také tehdy, pokud je útok úsp¥²ný s nezanedbatelnou pravd¥podobností. Pro jednoduchost budeme £asto pracovat s
ními stroji,
normalizovanými pravd¥podobnost-
u kterých jsou pro v²echny okamºité popisy práv¥ dv¥ instrukce s
SLOITOST PRO KRYPTOGRAFII
35
1 2 . Kaºdý pravd¥podobnostní stroj lze simulovat normalizovaným strojem s vysokou p°esností a konstantní ztrátou efektivity. Sta£í rozd¥lit pravd¥podobností
[0, 1]
interval
na podintervaly s délkami rovnými pravd¥podobnostem jednotlivých
bi konstruovat £íslo r = 0, b1 b2 . . . , dokud nedosáhneme p°esnosti umoº¬ující rozhodnout, v jakém intervalu se r nachází. Podobn¥ jako v p°ípad¥ vektoru voleb u nedeterministického moºných instrukcí a poté postupnou uniformní volbou bit·
stroje lze takto pravd¥podobností £ást výpo£tu koncentrovat na za£átek, kdy dojde k vygenerování pot°ebného po£tu náhodných bit·, a poté je jiº výpo£et deterministický. Uvaºujme n¥jaký výpo£et stroje
i1 , i2 , . . . , it .
nosti instrukcí
M ∈ PTM,
který sestává z aplikace posloup-
Pravd¥podobnost takového výpo£tu je
t Y
P (ik ).
k=1 ekneme, ºe
M ∈ PTM p°ijímá vstup x s pravd¥podobností p, p.
pokud sou£et prav-
d¥podobností p°ijímajících výpo£t· je
De nice 13.2.
L ∈ RP práv¥ kdyº existuje M ∈ PTM pracující v polynomiálním
£ase takový, ºe a) pokud b) pokud
x∈ / L, x ∈ L,
pak pak
M M
odmítne (vºdy), p°ijme s pravd¥podobností alespo¬ 1/2.
Stroje, které p°imají jazyky
RP
r
(zkratka pro andomized
polynomial
time )
nazýváme stroje typu MONTE CARLO. Platí pro n¥, ºe v nich nedochází k chybnému p°ijímání (no false positives), ale odmítnutí chybné být m·ºe. Snadno si rozmyslíme, ºe platí
Tvrzení 13.3.
P ⊆ RP ⊆ NP
1 2 v de nici RP je nepodstatná a m·ºe být nahrazena libovolnou hodnotou, polynomiáln¥ malou. Následující tvrzení ukazuje, ºe hodnota
V¥ta 13.4.
Jazyk L leºí v RP , práv¥ kdyº existuje M ∈ PTM pracující v polynomiálnám £ase a k ∈ N takové, ºe a) je-li x ∈ / L odmítne, 1 b) je-li x ∈ L p°ijme s pravd¥podobností alespo¬ . |x|k
D·kaz.
P°ímá implikace je z°ejmá.
M¥jme nyní stroj stroj
M0
M
vyhovující podmínkám v¥ty. Chceme ukázat, ºe existuje
odpovídající de nici. Takový stroj spo£ívá v opakování b¥hu stroje
Po£et opakování bude
nk ,
kde
n = |x|.
Stroj
M0
p°ijme práv¥ tehdy, pokud
M
M. p°i
opakovaných pokusech p°ijme alespo¬ jednou. Vzhledem k tomu, ºe M nemá ºádná chybná p°ijetí, nemá chybná p°ijetí ani M 0 . Spo£ítejme pravd¥podobnost chybného odmítnutí. Pravd¥podobnost chybného 1 odmítnutí v kaºdém kole b¥hu M je (1 − k ). P°edpokládáme, ºe jednotlivá kola n jsou nezávislá, a proto celková pravd¥podobnost chyby je nejvý²e
1 1− k n
nk <
1 . 2
Podobná úvaha umoº¬uje pravd¥podobnost omylu exponenciáln¥ sníºit, jak ukazuje následující tvrzení.
V¥ta 13.5.
Jazyk L leºí v RP, práv¥ kdyº existuje M ∈ PTM pracující v polynomiálnám £ase a k ∈ N takové, ºe
36
T
PÁN HOLUB a) b)
D·kaz.
je-li x ∈ / L odmítne, je-li x ∈ L p°ijme s pravd¥podobností alespo¬ 1 −
1 . 2|x|
Zde je z°ejmá implikace opa£ná.
Máme-li stroj s pravd¥podobností omylu men²í neº jedna polovina, opakujeme
n-krát,
jeho b¥h
1 n 2
£ímº sníºíme pravd¥podobnost omylu pod
.
co-RP, budeme jako obvykle mínit t°ídu jazyk·, jejichº komplement RP. Jazyk je tedy v co-RP pokud existuje stroj, který se nedopou²tí chybného
Ozna£ením je v
odmítnutí, a pravd¥podobnost chybného p°ijetí je men²í neº
1 2.
Pr·nik obou t°íd de nuje t°ídu
ZPP = RP ∩ co-RP. Stroje p°ijímající jazyky t°ídy
ZPP
z
( ero error
probability in polynomial time)
se nazývají algoritmy LAS VEGAS a m·ºeme si je p°edstavit jako sou£asn¥ b¥ºící dva stroje typu MONTE CARLO, jeden s jistým p°ijetím, druhý s jistým odmítnutím. S pravd¥podobností alespo¬ jedna polovina se po b¥hu algoritmu dozvíme výsledek. To tehdy, pokud jeden ze stroj· poskytne odpov¥¤, ve které se nemýlí. Název t°ídy je odvozen z faktu, ºe opakováním b¥hu algoritmu polynomiáln¥ mnohokrát se s exponenciální jistotou dozvíme správnou odpov¥¤. Z jiného pohledu, pokud necháme stroj b¥ºet tak dlouho, dokud nedá jistou odpov¥¤, bude pr·m¥rná doba £ekání polynomiální. (P°esn¥ji, pr·m¥rná doba £ekání bude dv¥ kola.) U t°íd
RP
a
ZPP
je nápadná asymetrie kladného a záporné odpov¥di. Taková
asymetrie je v n¥kterých p°ípadech p°irozená. Nap°. pokud se snaºíme ov¥°it prvo£íselnost n¥jakého £ísla tak, ºe ho zkusíme vyd¥lit n¥jakým men²ím £íslem. Pokud usp¥jeme, je z°ejmé, ºe £íslo prvo£íslem není. V opa£ném p°ípad¥ se m·ºeme domnívat, ºe prvo£íslem je, ale takový výsledek je vystaven omylu (v tomto p°ípad¥ samoz°ejm¥ mnohem v¥t²ímu, neº ºe prvo£ísla leºí v
1 2 ). Nap°. Rabin·v-Miller·v test uº ale ukazuje,
co-RP.
T°ídu, ve které je omyl rovnom¥rn¥ rozloºen do kladných i záporných odpov¥dí, de nujeme nyní.
De nice 13.6.
L ∈ BPP
práv¥ kdyº existuje
M ∈ PTM
pracující v polynomiál-
ním £ase takový, ºe a)
je-li
b)
je-li
x ∈ L, x∈ / L,
2 3, 1 pak pravd¥podobnost p°ijetí je nejvý²e . 3 pak pravd¥podobnost p°ijetí je alespo¬
2 3 podstatná. Pravd¥podobnost správné odpov¥di je op¥t moºné zvý²it opakováním b¥hu stroje. V tomto p°ípad¥ ale nelze Ani v p°ípad¥ této de nice není hodnota
£ekat na jist¥ správnou odpov¥¤. Musíme se spokojit s v¥t²inovou odpov¥dí, viz diskusi v kapitole o pravd¥podobnostních odhadech. Nemusí ale jít o prostou v¥t²inu. D·leºité je, ºe stroj se chová jinak pro vstupy z jazyka v porovnání s chováním pro vstupy mimo jazyk. Konkrétn¥ sta£í, ºe pravd¥podobnost odpov¥di ano je pro vstupy z jazyka o poznání pravd¥podobn¥j²í neº pro vstupy mimo jazyk. Význam výrazu o poznání je dán Chebyshevovým odhadem, jak ukazuje následující v¥ta a její d·kaz.
V¥ta 13.7. 1. 2.
Následující podmínky jsou ekvivalentní. L ∈ BPP Existuje M ∈ PTM pracující v polynomiálním £ase, c ∈ (0, 1) a k ∈ N takové, ºe 1 , a) je-li x ∈ L, pak pravd¥podobnost p°ijetí je alespo¬ c + |x|k b)
je-li x ∈ / L, pak pravd¥podobnost p°ijetí je nejvý²e c −
1 . |x|k
SLOITOST PRO KRYPTOGRAFII 3.
D·kaz.
37
Pro kaºdé ` ∈ N existuje M ∈ PTM pracující v polynomiálním £ase takový, ºe 1 a) je-li x ∈ L, pak pravd¥podobnost p°ijetí je alespo¬ 1 − |x|` , 2 1 b) je-li x ∈ / L, pak pravd¥podobnost p°ijetí je nejvý²e |x| . 2 ` Sta£í ukázat, ºe z 2. plyne 3. Ostatní implikace jsou z°ejmé.
M ∈ PTM spl¬uje p°edpoklady tvrzení 2. Zkonstruujeme stroj M 0 0 2k+` odpovídající pro dané ` poºadavk·m tvrzení 3. Práce stroje M spo£ívá v |x| 0 opakování b¥hu stroje M . M p°ijme vstup x práv¥ tehdy, kdyº M p°ijal x ve více 2k+` neº c|x| kolech. 0 Spo£t¥me, jaká je pravd¥podobnost chyby algoritmu M . P°edpokládejme, ºe x leºí v L, opa£ný p°ípad je analogický. Ozna£me Z náhodnou veli£inu de novanou Nech´ stroj
takto:
( Z= Ozna£me
X
1, 0,
pokud pokud
M M
p°ijal
nep°ijal
náhodnou veli£inu, která je sou£tem
po£et kol, ve kterých
M
x;
t(n)
x. kopií veli£iny
Z. X
je tedy
odpov¥d¥l správn¥.
X/|x|2k+` , ozna£me ji p, je p°itom stejná jako st°ední k 0 2k+` hodnota Z , tedy p ≥ c + 1/|x| . Stroj M odmítne x práv¥ tehdy, kdyº X/|x| ≤ c. Jednotlivé b¥hy stroje M povaºujeme za nezávislé a proto m·ºeme pouºít CherSt°ední hodnota veli£iny
no·v odhad. Dostáváme
" # ! X 1 |x|2k+` 1 X ≤ c ≤ Pr 2k+` − p ≥ ≤ 2 exp −2 ≤ |x|` . Pr k 2k 2k+` |x| |x| 2 |x| |x|
Pravd¥podobnost chyby algoritmu
M0
je tedy men²í neº
2−|x|
`
, coº jsme m¥li do-
kázat.
P°edchozí v¥tu m·ºeme shrnout slovy, ºe pokud umíme n¥jaký jazyk rozhodovat v polynomiálním £ase s pravd¥podobností úsp¥chu, který je alespo¬ o p°evrácenou hodnotu polynomu lep²í neº oby£ejné hádání, pak ho v polynomiálním £ase umíme rozhodovat s pravd¥podobností exponenciáln¥ blízkou jedné. 14. Neuniformní sloºitost V této kapitole se budeme zabývat velkorysou sloºitostní t°ídou, která slouºí spí²e jako horní odhad realistických výpo£t·. Tato t°ída do jisté míry poru²uje základní vlastnost algoritmu, totiº jeho uniformitu. Na vstupy r·zné délky pouºíváme odli²né algoritmy.
De nice 14.1.
L ∈ P/poly práv¥ kdyº existuje posloupnost Booleovských okruh· {Ci }∞ a polynom p takové, ºe Ci má práv¥ i vstup·, |Ci | ≤ p(i) a pro kaºdé x, i=1 |x| = i, Ci (x) = 1, práv¥ kdyº x ∈ L. Ekvivalentní charakteristika t°ídy
P/poly
je následující.
Tvrzení 14.2. L ∈ P/poly, práv¥ kdyº existuje polynomiální T ∈ DTM, posloupnost {an }∞ n=1 a polynom p takové, ºe pro v²echna n ∈ N je |an | ≤ p(n) a pro kaºdé x, |x| = n, platí, ºe x ∈ L, práv¥ kdyº M (x, an ) p°ijímá. D·kaz.
Je-li
L ∈ P/poly,
pak lze za
an
zvolit n¥jaký kód
Cn
a
M
bude zji²´ovat
jeho výstup. Pokud naopak
L
spl¬uje podmínky v¥ty, vytvo°íme obvod
Cn podobn¥ jako v M s konstantním
d·kazu Cookovy-Levinovy v¥ty tak, aby simuloval výpo£et stroje dodate£ným vstupem
an .
38
T
PÁN HOLUB Jak jsme jiº poznamenali, neuniformní t°ída je zaloºena na pouºívání nekone£n¥
mnoha r·zných algoritm·. Bu¤ nekone£n¥ mnoho obvod· nebo jeden algoritmus s nekone£n¥ mnoha nápov¥dami
an .
Jsou jen dv¥ omezení:
• •
pro vstupy stejné délky se pouºívá stejný obvod (stejná nápov¥da) obvody (nápov¥da) mají polynomiáln¥ omezenou velikost.
Z°ejm¥
P ⊂ P/poly, sta£í uvaºovat prázdnou nápov¥du. Nápov¥da umoº¬uje stroji rychle ur£it, jaká slova dané délky v jazyce leºí. Pokud je takových slov málo, m·ºe jako nápov¥da slouºit jejich seznam. ekneme, ºe jazyk
L
je
°ídký
slov délky
sparse ), pokud existuje polynom q takový, ºe pro kaºdé n je po£et L nejvý²e q(n). Z vý²e uvedené úvahy plyne, ºe P/poly obsahuje
(ang.
n
v
v²echny °ídké jazyky. Z toho plyne následující fakt.
Tvrzení 14.3.
Existuje nerekursivní jazyk L ∈ P/poly.
D·kaz. Sta£í ukázat, ºe existují nerekursivní °ídké G(x) jazyk K = {1 | x ∈ L}, kde L je nerekursivní + o£íslování Σ . Posloupnost okruh· který na vstupu
n
1
∞
{Cn }n=1 ,
jazyky. Uvaºme nap°. unární jazyk nad
Σ
a
G
pro kterou existuje polynomiální
vygeneruje kód
Cn
se nazývá
je efektivní
uniformní.
T°ídu
M ∈ DTM, P lze chápat
jako t°ídu jazyk·, pro které existuje uniformní posloupnosti okruh·. Totéº by platilo pro uniformní nápov¥dy. T°ída je tedy silná díky nápov¥dám, které jsou sice polynomiáln¥ dlouhé, ale nejsou generovatelné v polynomiálním £ase. O existenci takové obtíºn¥ nalezitelné nápov¥dy mluví následující tvrzení.
Tvrzení 14.4. D·kaz.
Nech´
rozhodující
L
BPP ⊆ P/poly
L ∈ BPP.
Pak podle V¥ty 10.9. existuje polynomiální
s pravd¥podobností chyby men²í neº
nejprve zvolí vektor náhodných bit·
M (x, r).
r,
2−|x| .
M ∈ PTM
P°edpokládejme, ºe stroj
a poté provede deterministický výpo£et
(Zde, p°ísn¥ vzato, p°edpokládáme, ºe stroj je normalizovaný.)
n existuje alespo¬ jeden vektor M , který se nedopou²tí chyby pro ºádný vstup délky n. Ten potom zvolíme jako nápov¥du an . Vznikne tak neuniformní stroj, který na vstupu x simuluje b¥h stroje M s p°íslu²ným vektorem náhodnosti a|x| . Chceme ukázat (nekonstruktivn¥), ºe pro kaºdé
voleb stroje
Ozna£me
Vx = {r | M (r, x) 6= χL (x)}. Bu¤
R
náhodná veli£ina, jejíº hodnotou je vygenerovaný vektor náhodnosti
libovolné
x
r.
Pro
platí
Pr [R ∈ Vx ] < 2−|x| , a tedy
Pr Rx ∈
[ |x|=n
Vx ≤
X
Pr [R ∈ Vx ] < 2n · 2−n = 1.
|x|=n
Pravd¥podobnost, ºe p°i náhodné volb¥ zvolíme vektor náhodnosti, který se mýlí pro alespo¬ jeden vstup, je men²í neº 1. Existuje tedy volba, pro kterou takový vstup neexistuje. To jsme cht¥li ukázat.
SLOITOST PRO KRYPTOGRAFII
39
15. Rozli²itelnost náhodných distribucí Ve v¥tách ampli kujících pravd¥podobnost jsme vid¥li, ºe libobolný polynomiální algoritmus, jehoº pravd¥podobnost úsp¥chu je alespo¬ p°evrácená hodnota polynomu, umoº¬uje sníºit pravd¥podobnost chyby exponenciáln¥. To motivuje následující de nici funkce, kterou, pokud vyjad°uje nap°. pravd¥podobnost úsp¥chu algoritmu, lze je²t¥ povaºovat za zanedbatelnou.
De nice 15.1. existuje
np ∈ N
µ : N → R+
je
zanedbatelná µ(n) <
pro v²echna
funkce, pokud pro kaºdý polynom
p
takové, ºe
1 p(n)
n ≥ np .
P°i výzkumu algoritmických problém· se obvykle snaºíme nalézt efektivní algoritmus a jeho neexistenci chápeme jako negativní výsledek. Situace je jiná v p°ípad¥ pseudonáhodných generátor·. Zde je naopak nemoºnost rozeznat pseudonáhodný výstup od skute£n¥ náhodné posloupnosti ºádoucí.
{Xn }n∈N , kde Xn nabývá {0, 1}`n , kde ` : N → N je n¥jaké zobrazení, typicky spl¬ující `(n) ≥ n (v¥t²inou budeme uvaºovat `(n) = n. Zejména nás bude zajímat, kdy je takový soubor blízko souboru p°íslu²ných rovnom¥rn¥ rozd¥lených náhodných veli£in {U`(n) }n∈N . Dále budeme pracovat se soubory náhodných veli£in
hodnot z
Blízkost soubor· m·ºe mít r·zné stupn¥.
De nice 15.2. •
Soubory jsou veli£iny
•
Nech´
Xn
a
Soubory jsou
{Xn }n∈N
a
{Yn }n∈N
jsou soubory náhodných veli£in.
identické, pokud pro v²echna n ∈ N platí Xn = Yn , tedy Yn mají stejné rozd¥lení. statisticky blízké, pokud je jejich statistická diference, de no-
vaná jako
∆X,Y (n) :=
1 2
X
|Pr [Xn = v] − Pr [Yn = v]| ,
v∈{0,1}n
zanedbatelná funkce.
•
Soubory jsou
výpo£etn¥ nerozli²itelné, D je
pokud pro kaºdý polynomiální prav-
d¥podobnostní algoritmus
δD,X,Y (n) := |Pr [D(Xn ) = 1] − Pr [D(Yn ) = 1]| zanedbatelná funkce. (Pravd¥podobnost bereme p°es rozd¥lení náhodných veli£in
•
Xn
a
Soubory jsou
Yn i p°es náhodnost b¥hu algoritmu D.) siln¥ výpo£etn¥ nerozli²itelné, pokud pro kaºdý soubor obvod·
C = {Cn }n∈N
polynomiální velikosti platí
σC,X,Y (n) := |Pr [Cn (Xn ) = 1] − Pr [Cn (Yn ) = 1]| zanedbatelná funkce. De nice pseudonáhodnosti se opírá o pojem (silné) výpo£etní nerozli²itelnosti.
De nice 15.3.
náhodný,
ekneme, ºe soubor náhodných veli£in
{Xn }n∈N je (siln¥) pseudo{U`(n) }n∈N náhod-
pokud je (siln¥) výpo£etn¥ nerozli²itelný od souboru
ných veli£in s uniformním rozd¥lením. Není t¥ºké ukázat, ºe statisticky blízké soubory jsou (siln¥) výpo£etn¥ nerozli²itelné. Opa£n¥ to ale neplatí, jak ukazuje následující v¥ta.
40
T
PÁN HOLUB
V¥ta 15.4.
Nech´ Un je rovnom¥rn¥ rozd¥lená náhodná veli£ina s hodnotami {0, 1}n . Pak existuje soubor náhodných veli£in {Xn }n∈N siln¥ výpo£etn¥ nerozli²itelný od {Un }n∈N takový, ºe n→∞ 1 ∆X,U (n) −−−−→ . 2
D·kaz.
Poloºme
n
m = 22.
Pro kaºdé
n
najdeme multimnoºinu
Sn = {s(i) | i = 1, 2, . . . , m} ⊆ {0, 1}n Xn = XSn = s(Um ). Jinak °e£eno, Xn vybírá uniformn¥ náhodn¥ Sn . Z°ejm¥ platí n 2 2 1 1 − n 1 X 1 ∆X,U (n) ≥ |Pr [Xn = v] − Pr [Un = v]| = 0 − 1 − n = − · 2 2 , 2 2 2 2 2
a de nujeme
prvek multimnoºiny
v ∈S / n
a tedy
n→∞
∆X,U (n) −−−−→
1 , 2
1 2. Mnoºinu Sn chceme zvolit tak, aby ºádný obvod velikosti nejvý²e
protoºe libovolná statistická diference je nejvý²e nerozli²il s nezanedbatelnou pravd¥podobností
Xn
n
28
s
n
vstupy
od rovnom¥rn¥ rozloºené ná-
hodné veli£iny. K tomu je nejprve t°eba získat n¥jaký odhad po£tu takových obvod·.
∗
Po£et booleovských obvod· velikosti nejvý²e k s n vstupy. Odhad provedeme pro k > n > 10 (to v na²em p°ípad¥ ur£it¥ nastává pro n ≥ 64). Nech´ (k∧ , k∨ , k¬ ) 3 ur£uje po£ty jednotlivých typ· vrchol·. Takových vektor· je mén¥ neº k . Kaºdý 2k vrchol má dva z k + n moºných vstup·, coº znamená mén¥ neº (k + n) r·zných propojení. Celkový po£et obvod· je tedy mén¥ neº 2
k 3 (k + n)2k < (2k)2k+3 = 2(2k+3) log 2k < 2k . M¥jme nyní n¥jaký pevn¥ daný obvod
Sn
je
C
∗ C . Chceme odhadnout, kolik r·zných mnoºin
schopno s nezanedbatelnou pravd¥podobností rozpoznat. P°esn¥ji, zkou-
mejme, pro kolik mnoºin
Sn
platí n
|Pr [C(XSn ) = 1] − Pr [C(Un ) = 1]| ≥ 2− 8 . Zde je
n
2− 8
vhodn¥ zvolená zanedbatelná funkce, shoda s velikostí obvodu je ne-
d·leºitá. Zkoumání provedeme pomocí pravd¥podobnostního odhadu: zjistíme s jakou pravd¥podobností bude obvodem odli²eno rovnom¥rn¥ náhodnými volbami prvk· ºovaná p°i volb¥
Sn
si .
XSn ,
pokud
Sn
vznikne nezávislými
V²imn¥me si, ºe pravd¥podobnost uva-
je zde pouze prost°edkem pro provedení po£etního argumentu,
Xn . n pC = Pr [C(Un ) = 1] a ozna£me Zi = C(si ) = C(Un ), i = 1, 2, . . . , 2 2 .
nesouvisí s náhodností veli£iny Ozna£me Veli£iny
Zi jsou tedy nezávislé náhodné veli£iny s Bernoulliho rozd¥lením se st°ední pC . Vzhledem k tomu, ºe XSn vybírá z mnoºiny Sn rovnom¥rn¥ náhodn¥,
hodnotou platí
n/2
2 1 X Zi . Pr [C(XSn ) = 1] = n 2 2 i=1 Máme tedy
n/2 1 2X |Pr [C(XSn ) = 1] − Pr [C(Un ) = 1]| = n Zi − pC , 2 2 i=1
SLOITOST PRO KRYPTOGRAFII
41
a z Chebyshevovy nerovnosti dostáváme
n/2 1 2X n/4 n n n Pr n Zi − pC ≥ 2− 8 ≤ 2 exp −2 · 2 2 · (2− 8 )2 < 2−2 . 2 2 i=1 Pro pravd¥podobnost nejvý²e
n/8
2
p, ºe XSn
bude rozeznáno od alespo¬ jednoho obvodu velikosti
, tedy s vyuºitím odhadu na po£et takových obvod· platí n/4
X
p<
n/8 2
2−2
< 2(2
)
n/4
· 2−2
= 1.
|C|<2n/8 Z toho plyne, ºe
XSn
pro n¥jaké
Sn
spl¬uje n
|Pr [C(XSn ) = 1] − Pr [C(Un ) = 1]| < 2− 8 pro v²echny obvody
C
velikosti nejvý²e
n
28.
Tím je d·kaz hotov.
De nice nerozli²itelnosti po£ítá s jediným vzorkem p°íslu²né náhodné veli£iny. Je proto p°irozené se ptát, jak je to s nerozli²itelností nerozli²itelných distribucí, pokud je moºné porovnávat r·zné, nezávislé vzorky. Odpov¥¤ není úpln¥ jednozna£ná. Je nap°íklad známo, ºe existuje soubor náhodných veli£in nerozli²itelný od
{Un }
a p°itom má nosi£
pravd¥podobností) velikost pouze
n2 .
sestávající z dvojic nezávislých kopií
Xn
{Xn },
který je výpo£etn¥
(tj. mnoºina hodnot s nenulovou
To ale znamená, ºe soubor
Xn
je od
o n (2) (1) Un , Un
n
(1)
(2)
Xn , Xn
o
rozli²itelný algorit-
mem, který na vstupu
(z1 , z2 ) testuje, zda z1 = z2 . Jak ale ukazuje následující v¥ta,
Xn
s takovou vlastností nelze sestrojit ºádným polynomiálním
náhodnou veli£inu
pravd¥podobnostním strojem ve smyslu následující de nice. ekneme, ºe soubor náhodných veli£in
{Xn }
je
polynomiáln¥ konstruovatelný, D takový, ºe náhodné
pokud existuje polynomiální pravd¥podobnostní algoritmus veli£iny
Xn
a
D(1n )
mají stejné rozd¥lení.
V¥ta 15.5 (O nerozli²itelnosti opakovanými experimenty). Nech´ jsou {Xn } a {Yn } polynomiáln¥ konstruovatelné výpo£etn¥ nerozli²itelné soubory náhodných veli£in. Pak jsou nerozli²itelné i polynomiáln¥ mnoha opakovanými experimenty. Tj. platí, ºe pro libovolný polynom q a libovolný polynomiální pravd¥podobnostní algoritmus D je h i h i ∆(n) = Pr D Xn(1) , . . . , Xn(q(n)) = 1 − Pr D Yn(1) , . . . , Yn(q(n)) = 1 , (i)
zanedbatelná funkce v n, kde Xn jsou vzájemn¥ nezávislé veli£iny se stejným roz(i) d¥lením jako Xn a Yn jsou vzájemn¥ nezávislé veli£iny se stejným rozd¥lením jako Yn . D·kaz.
∆(n) algoritmu D hybridní náhodné veli£iny = Xn(1) , . . . , Xn(i) , Yn(i+1) , . . . , Yn(q(n)) .
P°edpokládejme, ºe rozli²ovací výhoda
telná. Pro
i = 1, . . . , q(n) Hn(i)
Ozna£me
není zanedba-
de nujme tzv.
∆i (n), i = 0, 1, . . . , q(n) − 1,
výhodu, se kterou
D
rozli²uje dva sousední
hybridní soubory, tedy
h i i h ∆i (n) = Pr D Hn(i+1) = 1 − Pr D Hn(i) = 1 .
42
T
PÁN HOLUB
Platí
h i i h ∆(n) = Pr D Hn(q(n)) = 1 − Pr D Hn(0) = 1 q(n)−1 h i q(n)−1 h i X X Pr D Hn(k+1) = 1 − Pr D Hn(k) = 1 = k=0 k=0 q(n)−1
X
≤
∆i (n).
k=0 Z toho plyne, ºe alespo¬ jedna výhoda
∆j (n)
není zanedbatelná.
P°edpokládejme na chvíli, ºe víme, pro které algoritmus
Dj0 ,
který na vstupu
z
j je ∆j (n) nezanedbatelné, a uvaºme
spo£ítá
Dj0 (z) = D Xn(1) , . . . , Xn(j) , z, Yn(j+2) . . . , Yn(q(n)) . D0 platí i h i 0 h Pr Dj (Xn ) = 1 − Pr Dj0 (Yn ) = 1 = Pr D Hn(j+1) = 1 − Pr D Hn(j) = 1 Pro výhodu algoritmu
=∆j (n). Algoritmus
Dj0
tedy ukazuje, ºe
Protoºe v²ak
j
{Xn }
a
{Yn }
nejsou výpo£etn¥ nerozli²itelné.
neznáme, zkusíme ho uhodnout. Nech´ tedy algoritmus
prve s rovnom¥rnou pravd¥podobností zvolí
k ∈ {0, 1, . . . , q(n) − 1}
D00
nej-
a poté pro n¥j
Dk0 . Výhoda algoritmu D00 je nejmén¥ rovna výhod¥ algoritmu 0 Dj vynásobené pravd¥podobností volby k = j , tedy celkem spustí algoritmus
∆j , q(n) coº je stále je²t¥ nikoli zanedbatelná funkce. Protoºe jsme ukázali, ºe z p°edpokladu rozli²itelnosti polynomiálního po£tu vzork· plyne rozli²itelnost jednoho vzorku, je d·kaz u konce. Poznamenejme je²t¥, ºe polynomiální konstruovatelnost obou soubor· jsme vyuºili p°i de nici algoritmu
D0 ,
protoºe ten si musí p°íslu²né kopie
(i)
Xn
a
(i)
Yn
zkon-
struovat sám.
Dodatek k d·kazu.
Uvedený d·kaz motivuje konstrukci algoritmu
D00 ,
ale po£ítá
jeho výhodu p°íli² pesimisticky. Ve skute£nosti m·ºeme uváºit, ºe platí
Pr [D00 (Xn ) = 1] =
q(n) i 1 X h (k) Pr D Hn =1 , q(n) k=1
q(n)−1
Pr [D00 (Yn ) = 1] =
h i X 1 Pr D Hn(k) = 1 , q(n) k=0
a proto
|Pr [D00 (Xn ) = 1] − Pr [D00 (Yn ) = 1]| =
∆(n) . q(n)
16. Jednosm¥rné funkce a t¥ºký bit
De nice 16.1. •
Funkce
f : {0, 1}∗ → {0, 1}∗
spo£itatelná v polynomiálním £ase;
je
jednosm¥rná,
pokud je:
SLOITOST PRO KRYPTOGRAFII
•
43
t¥ºko invertovatelná. T.j. pro kaºdý pravd¥podobnostní polynomiální algoritmus
B
je
Pr
zanedbatelná funkce v
n.
x∼Un
B(f (x)) ∈ f −1 ◦ f (x)
jednosm¥rné permutace, tedy jednosm¥rné funkce, které
Zvlá²tním p°ípadem jsou
zachovávají délku vstupu a jsou prosté.
De nice 16.2. • •
Zobrazení
b : {0, 1}∗ → {0, 1}
je
t¥ºký bit
funkce
f,
pokud je:
spo£itatelné v polynomiálním £ase; není odhadnutelné s nezanedbatelnou výhodou. T.j. pro kaºdý pravd¥po-
B je Pr [B(f (x)) = b(x)] − x∼Un
dobnostní polynomiální algoritmus
zanedbatelná funkce v Je-li
f
1 2
n.
prostá, pak má t¥ºký bit, práv¥ kdyº je jednosm¥rná. Pokud by nebyla
jednosm¥rná, bylo by moºné hodnotu
b(x)
spo£ítat z
f (x)
invertováním. Pokud by
naopak bylo moºné s nezanedbatelnou pravd¥podobností spo£ítat libovolný bit bylo by moºné s nezanedbatelnou pravd¥podobností najít celé
xi ,
x.
Pro funkce, které prosté nejsou je situace sloºit¥j²í. De nice t¥ºkého bitu totiº poºaduje, aby bylo nalezeno
b(x) pro p°esn¥ to x, které bylo pouºito. Pokud má ale x a x0 s odli²nými hodnotami b(x) 6=
nap°.
f (x)
b(x0 ),
je odhad nemoºný. P°íkladem je funkce, která jen maºe první bit, který se
dva stejn¥ pravd¥podobné vzory
tak stává jejím t¥ºkým bitem, aniº by funkce byla jednosm¥rná. Pro kaºdou jednosm¥rnou permutaci tedy existuje n¥jaký bit vzoru, který je t¥ºkým bitem. Dokonce je takových hodn¥, ale apriori to o ºádném z nich nevíme. Sta£í uváºit funkci
f 0 (x, y) = (x, f (y)), kde f
je jednosm¥rná. Funkce
f0
je pak také
jednosm¥rná a p°itom prozrazuje celou první polovinu vstupu. Pon¥kud obecn¥ji se lze domnívat, ºe v¥t²ina binárních predikát· jednosm¥rné permutace je t¥ºká. Tato intuice je zaloºena na p°edpokladu, ºe z dostate£ného mnoºství binárních predikát· °et¥zce
x
je moºné
x
zrekonstruovat. Následující v¥ta tuto intuici potvrzuje
pro lineární predikáty a libovolnou jednosm¥rnou funkci, tedy nejen jednosm¥rnou permutaci.
V¥ta 16.3.
Nech´ je f libovolná jednosm¥rná funkce. De nujme funkci g p°edpisem g(x, r) := (f (x), r),
kde |x| = |r|. Pak je bodový sou£in vektor· x a r (modulo 2) t¥ºkým bitem funkce g. V¥ta °íká, ºe naprostá v¥t²ina kontrolních sou£t· argumentu funkce
f (x)
f.
x
je t¥ºkým bitem
Tvrzení lze reformulovat takto: Pokud p°i náhodné volb¥
rychle spo£ítat hodnotu
hx, ri
r
m·ºeme z
s nezanedbatelnou výhodou, m·ºeme s nezane-
dbatelnou pravd¥podobností zíkat i celé
x.
Vyslovme nejprve toto tvrzení pro xní
x.
V¥ta 16.4.
S pomocí orákula bx , pro které platí Pr [bx (r) = hx, ri] ≥
r∼Un
lze v £ase, který je polynomiální v
n ε,
1 +ε 2
a s pravd¥podobností alespo¬
ε2 2n
spo£ítat x.
44
T
PÁN HOLUB
D·kaz, ºe z V¥ty 16.4 plyne V¥ta 16.3.
Podstatou d·kazu je ukázat, jednoduchým
po£etním argumentem, ºe algoritmus odhadující
hx, ri
s nezandebatelnou pravd¥-
podobností, lze pouºít jako orákulum z V¥ty 16.4, které má pro nezanedbatelnou
x
£ást vstup·
nezanedbatelnou výhodu.
P°edpokládejme, ºe
hx, ri
není t¥ºký bit funkce
hx, ri
to dokazuje, tedy který vrací
γ
g.
Ozna£me
G
algoritmus, který
s nezanedbatelnou pravd¥podobností. Ozna£me
jeho výhodu, tedy
γ(n) := Sn
Pr [G(f (x), r) = hx, ri] −
x,r∼Un
1 . 2
x délky n, na kterých je G úsp¥²ný s pravd¥pon Sn má velikost alespo¬ γ(n) 2 · 2 , jinak by celková výhoda byla men²í neº γ(n)/2 · 1 + (1 − γ(n)/2) · γ(n)/2 < γ(n). Podle V¥ty 16.4 lze pro kaºdé x ∈ Sn v £ase, který je polynomiální v n/γ(n), a s pravd¥podobností alespo¬ poly(γ(n)/n) najít x s pomocí f (x): sta£í pouºít bx (r) := G(f (x), r). Protoºe x ∼ Un leºí v Sn s pravd¥podobností alespo¬ γ(n)/2 a protoºe je γ(n) nezanedbatelná, dostáváme spor s jednosm¥rností f . D·kaz V¥ty 16.4. Poloºme ` = log2 (n · ε−2 ) a zvolme uniformn¥ náhodn¥ a nezán n visle vektory s1 , s2 , . . . , s` ∈ {0, 1} (mluvíme o vektorech, protoºe budeme {0, 1} n chápat jako vektorový prostor F2 ). Dále zvolíme uniformn¥ a nezávisle bity σ1 , σ2 , . . . , σ` . Bit σi p°edstavuje ná² tip hodnoty hx, si i. P°edpokládejme, ºe skute£n¥ platí σi = hx, si i pro v²echna i = 1, . . . , `. Pravd¥podobnost takového úsp¥²ného tipu je 2 2−` ≥ εn . Pro dané k ∈ {1, 2, . . . , n} se nyní pokusíme spo£ítat xk , tj. k -tý bit vektoru x. Z linearity bodového sou£inu plyne, ºe správným odhadem bit· σi jsme získali hodnoty hx, ri pro v²echny vektory r , které leºí v lineárním obalu s1 , s2 , . . . , s` . Je-li L L J neprázdná podmnoºina {1, 2, . . . , `}, ozna£me rJ = j∈J sj . Bit σJ = j∈J σj je potom na²ím odhadem hodnoty hx, rJ i. Máme tedy polynomiáln¥ mnoho, konkrétn¥ 2` − 1 (ne nutn¥ r·zných) vektor· rJ a hodnot hx, rJ i, které pouºijeme k nalezení xk s pomocí rovnosti Ozna£me si
mnoºinu takových
γ(n)/2. algoritmu G
dobností alespo¬
Mnoºina
hx, rJ i ⊕ hx, rJ ⊕ ei i = hx, ek i = xk , ei
kde vektor
je kanonický bázový vektor. Hodnotu
známe, pro zji²t¥ní hodnoty Ozna£me
ZJ
hx, rJ ⊕ ek i
hx, rJ i podle bx .
p°edpokladu
pouºijeme orákulum
binární náhodnou veli£inu indikující správnost odpov¥di orákula
p°i na²em dotazu na
rJ ,
bx
a tedy i platnost rovnosti
hx, rJ i ⊕ bx (rJ ⊕ ei ) = xk . rJ ⊕ ek je díky si ∼ Un pro kaºdé J Pr [ZJ = 1] = 1/2 + ε. Pro K 6= J jsou navíc Vektor
rovnom¥rn¥ náhodný, platí tedy vektory
rJ ⊕ ek
rK ⊕ ek nezási . hodnot¥ xk s p°evahou a
vislé, protoºe se li²í o alespo¬ jedno rovnom¥rn¥ a nezávisle zvolené Máme tedy
m = 2` − 1
po dvou nezávislých hlasování o
správných odpov¥dí. Zd·razn¥me, ºe
ZJ
samoz°ejm¥ nejsou nezávislá, jsou ale jsou
po dvou nezávislá, coº sta£í k pouºití eby²evova odhad pro odhad pravd¥podobnosti omylu v¥t²inového rozhodnutí:
Pr
" X J
# X 1 ` 1 ZJ ≤ (2 − 1) ≤ Pr Zj − + ε · m ≥ m · ε 2 2 j ≤
m · Var[ZJ ] < m2 · ε2
1 4 n 2
− ε2 1 ≤ . − ε2 2n
SLOITOST PRO KRYPTOGRAFII
45
xk , k = 1, 2, . . . , n, je tedy alespo¬ 1 1 ε2 2 . Celková pravd¥podobnost nalezení x je tedy alespo¬ 2 · n .
Pravd¥podobnost, ºe nedojde k chyb¥ pro ºádné
(1 −
1 n 2n )
≥
D·leºitým kryptogra ckým primitivem, pro který se pouºívá t¥ºký bit jednosm¥rné funkce, je
závazek.
Pouºívá se v situaci, kdy strana
A
chce p°edat n¥jakou
zprávu (v de nici níºe se jedná o jednobitovou zprávu) stran¥ nemohla zprávu dozv¥d¥t, dokud k tomu nedá
A
sou£asn¥, aby
De nice 16.5.
A
B
tak, aby se
B
dodate£ný souhlas (tajnost), a
nemohla zprávu dodate£n¥ zm¥nit (závaznost). ekneme, ºe polynomiální pravd¥podobnostní algoritmus
tový závazek, pokud pro kaºdé m ∈ {0, 1} a kaºdé x, x0 ∈ {0, 1}∗ • (závaznost): Z(x, m) 6= Z(x0 , 1 − m) • (tajnost) Soubory náhodných veli£in {Zx∼Un (x, 0)}n
a
Z
je
bi-
platí:
{Zx∼Un (x, 1)}n
jsou výpo£etn¥ nerozli²itelné. Takovým typem závazku k hodnot¥ hodnota
f (x).
x je pro kaºdou jednosm¥rnou prostou
funkci
Abychom tento fakt vyuºili pro vytvo°ení bitového závazku sta£í
pouºít libovolný t¥ºký bit
b
funkce
f.
Závazek má potom podobu
Z(m, x) = (z1 , z2 ) := (f (x), m ⊕ b(x)) . Autorizací k otev°ení závazku je je rovnost
f (x) = z1 ,
x,
protoºe platí
m = z2 ⊕ b(x).
Ov¥°ením pravosti
která zaru£uje i závaznost, protoºe platí pouze pro jediné
x.
17. Pseudonáhodné generátory
De nice 17.1.
(Neuniformn¥ silný) pseudonáhodný generátor je deterministický G, který vstupy délky n prodluºuje na výstupy délky ºe soubor {G(Un )}n∈N je (siln¥) pseudonáhodný.
polynomiální algoritmus
`(n) > n
tak,
Lze ukázat, ºe pseudonáhodné generátory existují, práv¥ kdyº existují jednosm¥rné funkce. Pro jednoduchost budeme uvaºovat siln¥j²í p°edpoklad, totiº existenci jednosm¥rných permutací (obecné tvrzení p°iná²í °adu nep°íjemných technických komplikací). Za tohoto p°edpokladu je snadné sestrojit pseudonáhodný generátor, jak ukazuje následující v¥ta. Z°et¥zení bit· budeme kv·li lep²í £itelnosti zna£it te£kou.
Tvrzení 17.2.
Nech´ je f jednosm¥rná permutace a b její t¥ºký bit. Pak je zobrazení G : x 7→ f (x) · b(x)
pseudonáhodný generátor. D·kaz. Chceme ukázat, ºe schopnost rozli²it f (x) · b(x) od náhodné posloupnosti délky |x| + 1 znamená schopnost uhodnout b(x) s pomocí f (x). P°edpokládejme tedy, ºe G není pseudonáhodný generátor a ºe D je algoritmus, který to dokazuje, tedy pro který platí
Pr [D (f (x) · b(x)) = 1] − Pr [D (y 0 ) = 1] = ε(n), x∼Un 0 y ∼Un+1 kde
ε není zanedbatelná funkce. Tuto rovnost m·ºeme pro lep²í porozum¥ní p°epsat
jako
Pr D y · b ◦ f −1 (y) = 1 − Pr [D (y · σ) = 1] = ε(n). y∼Un y∼Un σ∼U 1
46
T
PÁN HOLUB
Protoºe s pravd¥podobností
Pr [D (y · σ) = 1] =
y∼Un σ∼U1
1/2
platí
σ = b ◦ f −1 (y),
platí také
h i 1 1 Pr D y · b ◦ f −1 (y) = 1 + Pr D y · b ◦ f −1 (y) = 1 , 2 y∼Un 2 y∼Un
odkud dostáváme
i h Pr D y · b ◦ f −1 (y) = 1 − Pr D y · b ◦ f −1 (y) = 1 = 2 ε(n) . y∼Un y∼Un Rozli²ova£
b(x).
D
nyní mírn¥ modi kujeme na algoritmus
Na vstupu
y ∈ {0, 1}n
zvolí algoritmus
A
A,
který bude z
f (x) hádat σ a poté
uniformn¥ náhodný bit
rozhodne takto:
( A(y) =
σ, σ,
pokud pokud
D(y · σ) = 1; D(y · σ) = 0.
A. Pr A(y) = b ◦ f −1 (y) = y∼Un = Pr D(y · σ) = 1 ∧ σ = b ◦ f −1 (y) + Pr D(y · σ) = 0 ∧ σ = b ◦ f −1 (y) =
Spo£ítejme úsp¥²nost algoritmu
y∼Un σ∼U1
y∼Un σ∼U1
= Pr D(y · b ◦ f −1 (y)) = 1 ∧ σ = b ◦ f −1 (y) + y∼Un σ∼U1
+ Pr
h
y∼Un σ∼U1
i D(y · b ◦ f −1 (y)) = 0 ∧ σ = b ◦ f −1 (y) =
h i 1 1 Pr D(y · b ◦ f −1 (y)) = 1 + Pr D(y · b ◦ f −1 (y)) = 0 = 2 y∼Un 2 y∼Un σ∼U1 σ∼U1 i h 1 1 = Pr D(y · b ◦ f −1 (y)) = 1 + 1 − Pr D(y · b ◦ f −1 (y)) = 1 = y∼Un 2 y∼Un 2 σ∼U1 σ∼U1 h i 1 1 = + Pr D y · b ◦ f −1 (y) = 1 − Pr D y · b ◦ f −1 (y) = 1 = y∼Un 2 2 y∼Un 1 = ± ε(n) . 2 =
Výhoda
Pr A(y) = b ◦ f −1 (y) − y∼Un algortimu
A
1 2
tedy není zanedbatelná funkce, coº je spor s p°edpokladem, ºe
t¥ºký bit funkce
f.
b
je
Shr¬me je²t¥ jednou sd¥lení p°edchozí v¥ty. T¥ºký bit se chová jako nový náhodný bit, p°estoºe je dán z prvních
n bit· deterministicky. Jako náhodný se chová
práv¥ proto, ºe je t¥ºký: jeho (jednozna£ná) souvislost s p°edchozím vstupem totiº není algoritmicky detekovatelná s nezanedbatelnou výhodou. Nevýhodou práv¥ zkonstruovaného pseudonáhodného generátoru je jeho krátkost, produkuje pouze jediný nový náhodný bit. Sta£í ale my²lenku konstrukce libovoln¥ (polynomiáln¥-krát) vhodným zp·sobem opakovat, abychom dostali libovolný (polynomiální) po£et náhodných bit·. Jako v p°ípad¥ nerozli²itelnosti nerozli²itelných distribucí opakovanými experimenty, ani v tomto p°ípad¥ není opakováním naru²ena pseudonáhodnost. D·kaz pouºívá techniku hybridních distribucí podrobn¥ vyloºenou v d·kazu nerozli²itelnosti opakovanými experimenty.
SLOITOST PRO KRYPTOGRAFII
47
Tvrzení 17.3.
Nech´ je G pseudonáhodný generátor s prodluºovací funkcí `(n) = n + 1 a nech´ `0 je libovolný polynom. De nujme zobrazení G0 p°edpisem G0 (s) = σ1 (s) · σ2 (s) · · · σ`0 (|x|) (s),
kde x0 = s, i = 1, 2, . . . , `0 (|x|) .
G(xi−1 ) = xi · σi (s),
Pak je G0 pseudonáhodný generátor. D·kaz.
Nech´
X1 , X2 , . . . , X`(n)
U1 .
ozna£ují nezávislé kopie náhodné prom¥nné
Chceme ukázat, ºe nelze s nezanedbatelnou výhodou rozli²it
X1 , . . . , X`(n)
od σ1 (s), . . . , σ`(n) (s) pro s ∼ Un . Zd·razn¥me, ºe σi (s) jsou náhodné veli£iny závislé na uniformní volb¥ téhoº s, a jsou tedy zcela závislé. De nujme hybridní distribuce
H (i) = X1 , X2 , . . . , Xi , σ1 (s), σ2 (s), . . . , σ`(n)−i (s) . 0
D, který rozli²uje H (0) od H (` (n)) s nezandebatelnou výhodou, rozli²uje (i) (i+1) s nezanedbatelnou výhodou také n¥jaké H od H . Ukaºme, ºe to umoº¬uje s nezanedbatelnou výhodou rozli²it G(x) od Un+1 ve sporu s p°edpokladem, ºe G je Algoritmus
pseudonáhodný generátor.
i, coº se stane s nezanedbatelnou prav1/`0 (n). Pro dané y ·σ , kde |y| = n a |σ| = 1, nyní necháme algoritmus
P°edpokládejme, ºe jsme zvolili správné d¥podobností
D
rozhodnout vstup
X1 , X2 , . . . , Xi , σ, σ1 (y), σ2 (y), . . . , σ`(n)−i−1 (y) . y · σ ∼ Un+1 jedná se o H (i+1) . Je-li naopak y · σ = G(s) pro s ∼ Un , H , protoºe σ = σ1 (s) a σi (y) = σi+1 (s). Tím je d·kaz hotov.
Je-li o
(i)
jedná se
18. D·kazové systémy
De nice 18.1.
Interaktivní Turnig·v stroj
je vícepáskový
pravd¥podobnostní
Turing·v stroj se vstupem a výstupem, který krom¥ vstupní pásky (kterou nazýváme
ve°ejná, výstupní pásky a pracovních pásek obsahuje je²t¥ • dodate£nou vstupní pásku, kterou nazýváme soukromá, • vstupní komunika£ní pásku, která je jen ke £tení, • výstupní komunika£ní pásku, která je jen ke psaní, • stavový bit, tj. pásku sestávající z jednoho polí£ka, které
nese nulu nebo
jedni£ku. Stroji je p°i°azena
identita
nula nebo jedna.
Program obsahuje instrukce pouze pro p°ípad, ºe stavový bit je roven identit¥ stroje. V takovém p°ípad¥ °íkáme, ºe stroj pracuje, v opa£ném p°ípad¥ je Mnoºinu interaktivních Turingových stroj· ozna£me
ITM
ne£inný.
De nice interaktiv-
ního stroje, stejn¥ jako jeho název, ukazuje, ºe smysl jeho výpo£tu spo£ívá v komunikaci s jiným interaktivním strojem.
De nice 18.2. (A, B), • • • •
Interaktivní systém
je dvojice interaktivních Turingových stroj·
které mají opa£nou identitu, sdílejí ve°ejnou vstupní pásku, sdílejí stavový bit, vstupní komunika£ní páska stroje
B
a naopak.
A
je výstupní komunika£ní páskou stroje
48
T
PÁN HOLUB Díky opa£né identit¥ stroj· je vºdy jeden ze stroj· interaktivního systému ne-
£inný a jeden pracuje. Výpo£et interaktivního systému tedy sestává z n¥kolika
fází,
coº jsou souvislé úseky, ve kterých se stavový bit nem¥ní. Ve chvíli, kdy pracující stroj p°epí²e stavový bit, dostane se do ne£innosti a za£íná dal²í fáze, ve které pracuje druhý stroj aº do chvíle, kdy p°epí²e stavový bit zp¥t. Stroje si takto vzájemn¥ udílejí slovo . Pro posuzování £innosti interaktivního systému jsou d·leºité následující konvence:
• •
Výstupem interaktivního výpo£tu je výstup stroje
B.
Náro£nost výpo£tu je posuzována pouze nároky stroje je tedy po£et krok·, které provedl stroj
B
B . asová náro£nost
(kdyº pracoval).
Asymetrická de nice náro£nosti interaktivního systému souvisí s tím, ºe tyto systémy chápeme jako komunikaci mezi
x interaktivní d·kazové systémy.
(stroj B) tvrzení o p°ítomnosti vstupu nazýváme
dokazovatelem
(stroj A) a
ov¥°ovatelem
L.
Proto je také
v rozhodovaném jazyku
Na dokazovatele neklademe ºádná omezení, pokud jde o výpo£etní sílu, m·ºeme
A
tedy p°edpokládat, ºe kladu, ºe
L
je schopen ov¥°it, zda
x ∈ L
(za minimálního p°edpo-
je rekursivní). Pokud by tedy ov¥°ovatel mohl spoléhat na informaci
poskytovatele, bylo by snadné rozhodovat libovolný rekursivní jazyk. Smysl interaktivních d·kazových systému v²ak spo£ívá v tom, ºe ov¥°ovatel je informaci týkající se vstupu schopen ov¥°it. Vyºaduje tedy od dokazovatele d·kaz pro jeho tvrzení. Od systému vyºadujeme t°i vlastnosti:
• efektivita (e ciency ): ov¥°ovatel pracuje rychle; • úplnost (completeness ): ov¥°ovatel p°ijme platný d·kaz; • spolehlivost (soundness ): ov¥°ovatel nep°ijme neplatný d·kaz
od ºádného
dokazovatele, který se ho snaºí p°esv¥d£it o nesprávném tvrzení. Tento neformální popis vede k následující de nici sloºitostní t°ídy
De nice 18.3. • • •
Jazyk
IP.
L leºí v IP, pokud existuje interaktivní systém (A, B), který
(efektivita) pracuje v polynomiálním £ase;
(A, B) p°ijme vstup x ∈ L s pravd¥podobností alespo¬ 23 ; (spolehlivost) pokud x ∈ / L, pak pro libovolný interaktivní stroj A∗ je prav1 ∗ d¥podobnost, ºe systém (A , B) p°ijme x, men²í neº . 3
(úplnost) systém
Tvrzení 18.4. (1) (2)
BPP ⊆ IP NP ⊆ IP
D·kaz. (1) Nech´
L ∈ BPP
B ho rozhoduje ve smyslu de nice BPP. Pak (∅, B) rozhoduje L ve smyslu De nice 18.3, kde ∅ zna£í, prob¥hne v jediné fázi. B je schopen rozhodnout L bez pomoci a stroj
interaktivní systém ºe výpo£et
dokazovatele. (2) Nech´
x
L ∈ NP.
Interaktivní systém, který rozhoduje
následovn¥. Výpo£et zahajuje stroj
je sv¥dkem pro relace
x.
Stroj
A
A,
poté ov¥°í, ºe
L
pracuje na vstupu
který sd¥lí stroji
(x, y) ∈ RL ,
kde
B slovo y , které RL je sv¥decká
L.
Postup je efektivní, nebo´ a skute£ností, ºe
A
RL
je v
P.
Úplnost je dána existencí sv¥dka
ho m·ºe díky své neomezené výpo£etní síle nalézt.
Spolehlivost plyne z toho, ºe pro nep°ijme, a´ je zpráva od
A
x∈ /L
ºádný sv¥dek neexistuje a tudíº
B
jakákoli.
SLOITOST PRO KRYPTOGRAFII
49
L ∈ NP
V²imn¥te si, ºe oba stroje b¥hem výpo£tu rozhodujícího
pracují deter-
ministicky. Bez d·kazu uvádíme v¥tu, která t°ídu
IP
uvádí do jasné souvislosti s determi-
nistickými t°ídami.
V¥ta 18.5 (Shamir).
IP = PSPACE
BPP a NP jsou snadné. Ukáºeme d·kaz pro grafový neisomor smus, NP nebo v BPP. Budeme p°edpokládat, ºe vrcholy grafu jsou £ísla {1, . . . , n}. Grafy G1 a G2 jsou isomorfní, pokud mají stejný po£et prvk· n a existuje π ∈ Sn taková, ºe (i, j) je hrana G1 , práv¥ kdyº (π(i), π(j)) je hrana G2 . Potom pí²eme G1 ∼ = G2 a π(G1 ) = G2 . Grafový neisomor smus je tedy jazyk D·kazy pro
coº je problém, o kterém není známo, zda leºí v
= {(G1 , G2 ) | G1 ∼ 6 G2 }. =
GraphNI
x ∈r x je uniformn¥ náhodn¥ zvolený prvek mnoºiny X .
Jádro interaktivního d·kazu je popsáno následujícím schématem. Zápisem
X
budeme zna£it skute£nost, ºe
Stroj A
Stroj B VSTUP:
(G0 , G1 ) i ∈r {0, 1} π ∈r Sn spo£ti H = π(Gi )
zvol
zvol
H ϕ takové, ºe ϕ(H) = Gj , j ∈ {0, 1} najdi
j ov¥°, ºe
Tvrzení 18.6. D·kaz.
GraphNI
j=i
∈ IP B (ov¥°ovatel) i = j . Ukáºeme, ºe p°ijímá GraphNI. Efektivita
Uvaºujme dv¥ kola vý²e uvedené komunikace, p°i£emº stroj
p°ijme, pokud v obou kolech platí je z°ejmá.
(G1 , G2 ) ∈ GraphNI. Graf H je tedy isomorfní s Gi a nikoli s G1−i . Pokud ϕ(H) = Gj , platí i = j . Stroj B tedy vstup p°ijme (s pravd¥podobností 1).
Nech´ tedy
Tím je dokázána úplnost systému. P°edpokládejme nyní
(G1 , G2 ) ∈ / GraphNI, tedy G1 ∼ = G2 . Nech´ Mi , i ∈ {0, 1},
je multiset
Mi = {π(Gi ) | π ∈ Sn }. (Multiset je mnoºina, která m·ºe stejný prvek obsahovat vícekrát, tedy
|Mi | = n!,
p°estoºe n¥které permutace mohou de novat tentýº graf .) Snadno nahlédneme, ºe
M1 a M2 jsou identické a H je náhodn¥ uniformn¥ zvolený prvek M = M1 = M2 . Pro jakýkoli stroj P ∗ bude tedy náhodná veli£ina j nezávislá na volb¥ i. Vzhledem k tomu, ºe i je voleno náhodn¥ uniformn¥, je pravd¥podobnost i = j
multisety
1 1 2 . Pravd¥podobnost p°ijetí vstupu je tedy 4 . Tím je dokázána spolehlivost systému. p°esn¥
Zajímavou vlastností p°edchozího d·kazu je fakt, ºe stroj
B,
p°estoºe výpo£tem
s velkou pravd¥podobností (kterou lze opakováním exponenciáln¥ p°iblíºit jedné) ov¥°í, ºe
x ∈ L, nezíská tím ºádnou informaci, kterou by bylo moºné x ∈ L podpo°it,
50
T
PÁN HOLUB
pouºitelnou v situaci, kdy se
B
octne v roli dokazovatele. Ov¥°ovatel se nedozví nic,
co by sám nemohl spo£ítat, krom¥ samotného faktu
x ∈ L.
Interaktivní výpo£et mající tuto pozoruhodnou vlastnost se nazývá
lovou znalostí.
De nice 18.7. znalostí
d·kaz s nu-
Formáln¥ je zachycen následující de nicí. Interaktivní d·kazový systém
L,
(zero knowledge proof ) pro jazyk
(A, B)
se nazývá
d·kaz s nulovou L ve smyslu
pokud rozhoduje jazyk
De nice 18.3 a navíc existuje (oby£ejný) polynomiální pravd¥podobnostní stroj
M ∈ PTM takový, ºe pro v²echny interaktivní stroje B ∗ platí • S pravd¥podobností nejvý²e 21 bude výstupem stroje M speciální symbol ⊥. ekneme, ºe výpo£et stroje M selhal. • Platí {M (x) | M (x) 6= ⊥}x∈L ∼ {σF (A, B ∗ )(x)}x∈L , ∗ ∗ kde σF (A, B )(x) je záv¥re£ný snímek stroje B po výpo£tu interaktivního ∗ d·kazového systému (A, B ) na vstupu x. P°edchozí de nice je jakýmsi polotovarem, který bude dokon£en up°esn¥ním významu symbolu
∼. Uv¥domme si, ºe {M (x)}x∈L
náhodných veli£in daných náhodným chováním Symbolu
∼
{σF (A, B ∗ )(x)}x∈L ∗ stroj· M , A a B . a
jsou soubory
m·ºe odpovídat jeden ze stup¬· blízkosti distribucí.
∼ rovnost soubor· náhodných veli£in, dostáváme de nici d·kazu s dokonale nulovou znalostí. • Znamená-li ∼ statistickou blízkost soubor· náhodných veli£in, dostáváme de nici d·kazu s tém¥° dokonale nulovou znalostí. • Znamená-li ∼ výpo£etní nerozli²itelnost soubor· náhodných veli£in, dostáváme de nici d·kazu s výpo£etn¥ nulovou znalostí. T°ídu jazyk·, pro n¥º existuje d·kaz s dokonale nulovou znalostí, zna£íme PZK, t°ídu jazyk·, pro n¥º existuje d·kaz s tém¥° dokonale nulovou znalostí zna£íme SZK a t°ídu jazyk·, pro n¥º existuje d·kaz s výpo£etn¥ nulovou znalostí zna£íme CZK. Stroj M v de nici d·kazu s nulovou znalostí se nazývá simulátor. Je to stroj, ∗ který na vstupu x ∈ L je schopen pro libovolného ov¥°ovatele B - tedy i takového, který se ve snaze o získání n¥jaké informace nechová podle pravidel systému (A, B) •
Znamená-li
- vypsat jeho záv¥re£ný snímek. Ten mimo jiné obsahuje komunika£ní pásky, a znalosti. Cokoli, co se
B
∗
od
B∗
od A. Tím je uchopena my²lenka nulové A dozv¥d¥l si mohl vygenerovat sám pomocí simulátoru
tedy ve²kerou informaci, kterou získal
M. Nabízí se otázka, zda tedy
M
neumí sám rozhodovat jazyk
je t°eba zd·raznit, ºe simulátor je úsp¥²ný
L.
pouze na vstupech
Jako odpov¥¤
x ∈ L,
tedy za
p°edpokladu oné jediné informace, kterou mu má d·kaz poskytnout. Pokud
M
m·ºe se
x∈ / L,
chovat zcela libovoln¥.
Nyní m·ºeme vyslovit tvrzení, které bylo motivací na²í de nice d·kazu s nulovou znalostí.
Tvrzení 18.8. GraphNI
D·kaz.
∈ PZK.
M se m·ºe chovat jako B ∗ s A. Za p°edpokladu (G0 , G1 ) ∈ GraphNI je v²ak simulace zpráv A snadná: stroj A vºdy po²le j , které je rovno i, coº je hodnota stroji M známá z p°edchozí simulace. Popí²eme simulátor
M
ov¥°ovatele
B∗.
Stroj
tou výjimkou, ºe si musí sám generovat zprávy od
P°íklad GraphNI je zvlá²tní tím, ºe
A
svou znalost £erpá ze své neomezené
výpo£etní síly. Vlastn¥ tedy neexistuje ºádný d·kaz, který by mohl být prozrazen. Následující tvrzení ukazuje, ºe existují i jazyky, které jsou v
NP a sou£asn¥ v PZK.
SLOITOST PRO KRYPTOGRAFII
51
x x ∈ L
V tomto p°ípad¥ si m·ºeme p°edstavovat, ºe dokazovatel má pro daný vstup k dispozici na svém soukromém vstupu sv¥dka
y
v polynomiálním £ase. Jako d·kaz ov²em
y.
Je tedy schopen ov¥°it
pouºít nem·ºe, protoºe by se zjevn¥
nejednalo o d·kaz s nulovou znalostí. P°íkladem bude komplement GraphNI, tedy problém grafového isomor smu
GraphISO
= {(G0 , G1 ) | G0 ∼ = G1 }.
Tvrzení 18.9. GraphISO
D·kaz.
∈ PZK
Popí²eme d·kaz s dokonale nulovou znalostí pro GraphISO. D·kaz spo£ívá
ve dvojím opakování následující komunikace:
Stroj A
Stroj B
SOUKROMÝ VSTUP: isomor smus
ϕ : G0 → G1
VSTUP:
(G0 , G1 )
j ∈r {0, 1} π ∈r Sn spo£ti H = π(Gj ) zvol
zvol
H zvol
i ∈r {0, 1}
i
if i = j then ψ := π else ψ := π ◦ ϕ(−1)
j+1
Stroj
B
ψ
p°ijme, pokud v obou kolech
ov¥°, ºe
ψ(Gi ) = H
ψ(Gi ) = H .
Systém je z°ejm¥ efektivní a úplný (platný vstup p°ijímá s pravd¥podobností 1).
G0 a G1 nejsou isomorfní. Pak je zpráva H , bez ohledu na A∗ , isomorfní nejvý²e jednomu z graf·. S pravd¥podobností alespo¬ 12 tedy ov¥°ovatel B zvolí i, pro které neexistuje ºádné ψ spl¬ující poºadavek ψ(Gi ) = H . V takovém p°ípad¥ B odmítne. Ve dvou kolech tedy odmítne s pravd¥podobností P°edpokládejme, ºe
postup
3 4 . Tím je dokázána spolehlivost. Zbývá ukázat nulovou znalost. Nech´
alespo¬
G0 ∼ = G1 . Simulátor M m·ºe simulovat −1 celý výpo£et s výjimkou situace, kdy A volí ψ = π ◦ ϕ , tedy v situaci, kdy i 6= j . ∗ Vzhledem k tomu, ºe A postupuje podle pravidel, má B p°i volb¥ i k dispozici náhodný prvek multisetu
zcela nezávisle na náhodné
M = {π(Gi ) | π ∈ Sn } hodnot¥ i (podobn¥ jako v
d·kazu Tvrzení 18.8). Prav1 1 2 . S pravd¥podobností 2 tedy M není schopen dokon£it simulaci jednoho kola a jeho výpo£et selºe. Celková pravd¥po1 dobnost simulace dvoukolového algoritmu je tedy 4 . Sta£í t°i opakování pokusu o 1 simulaci, aby se pravd¥podobnost úsp¥chu dostala nad . M tedy opakuje celý po2 stup t°ikrát a vytiskne ⊥ pouze v p°ípad¥, ºe v²echny pokusy selhaly. Jinak vytiskne ∗ výstupní snímek B po úsp¥²ném pokusu. d¥podobnost, ºe zvolí
i 6= j ,
je tedy p°esn¥
D·kazy s nulovou znalostí existují pro v²echny jazyky v slevit z dokonale nulové na výpo£etn¥ nulovou znalost.
V¥ta 18.10.
NP ⊂ CZK.
NP.
Musíme ov²em
52
T
PÁN HOLUB
Nástin d·kazu.
D·kaz této v¥ty neuvedeme v úplnosti. Ukáºeme v²ak d·kaz s nu-
lovou znalostí pro
NP-úplný jazyk 3Coloring. Jedno kolo interaktivního výpo£tu
vypadá takto:
Stroj A
Stroj B
SOUKROMÝ VSTUP: obarvení
γ : V → {0, 1, 2}
VSTUP:
G = (V, E)
zvol π ∈r S3 ∀k ∈ V vytvo°: závazek ϕk pro π ◦ γ(k) s klí£em κ(k)
{ϕk | k ∈ V } zvol
(i, j) ∈r E
(i, j)
(κi , κj ) otev°i závazky
ϕi
a
ϕj
a ov¥°, ºe
π ◦ γ(i) 6= π ◦ γ(j) Procedura se opakuje
2 |E|
krát. Stroj p°ijme pokud podmínka je spln¥na ve
v²ech kolech, jinak odmítne. Efektivita i úplnost (s pravd¥podobností jedna) se ov¥°í snadno. Ov¥°me spolehlivost. Nech´ graf nemá obarvení t°emi barvami. Pak je závazek
(ϕ1 , . . . , ϕ|V | )
nesprávný (nesmyslný nebo nespl¬ující podmínku obarvení) pro ale-
spo¬ jednu hranu. Pravd¥podobnost, ºe to stroj
2 |E|
B
odhalí je tedy alespo¬
1 |E| . Po
opakováních je pravd¥podobnost nesprávného p°ijetí
1−
1 |E|
2|E| ,
1 4. Nazna£me d·kaz nulové znalosti. Simulátor M zvolí náhodn¥ uniformn¥ hranu (i0 , j 0 ) ∈ E a dvojici (c1 , c2 ) dvou rozdílných barev. Vytvo°í závazek ϕi0 a ϕj 0 pro 0 0 hodnoty c1 a c2 . Závazky ϕk , k 6= i , j zvolí libovoln¥. Tím simuluje £innost stroje coº je men²í neº
A. B ∗ . Ta m·ºe být jakákoli, ale kon£í výstupem (i, j) ∈ A. Pokud (i, j) 6= (i0 , j 0 ), simulace selºe M . V opa£ném
Poté simuluje £innost stroje
E,
který
B
∗
posílá stroji
M
p°ípad¥ vrátí
p°íslu²né klí£e a dokon£í simulaci jednoho kola.
1 |E| . Polynomiáln¥ mnoho opakování tedy díky Chernoovu odhadu zaru£uje více neº polovi£ní pravd¥podobPravd¥podobnost úsp¥²nosti simulace jednoho kola je
nost alespo¬
|E|
úsp¥²ných simulací.
Zbývá ov¥°it, ºe výstup simulátoru je výpo£etn¥ nerozli²itelný od záv¥re£ného snímku skute£ného výpo£tu. Je z°ejmé, ºe d·kaz není s dokonale nulovou znalostí, není ani s tém¥° dokonale nulovou znalostí. Závazek
ϕ
stroje
A
statisticky velmi li²í. Závazek
hodnot, zatímco závazek vení grafu
G.
ϕ
0
ϕ0
stroje
M
se totiº od závazku
je závazkem z velké £ásti náhodných
ϕ je závazkem malé podmnoºiny hodnot - korektních obar-
SLOITOST PRO KRYPTOGRAFII Náhodné veli£iny
ϕ
a
ϕ0
53
jsou ov²em výpo£etn¥ nerozli²itelné díky tomu, ºe zá-
vazky r·zných hodnot jsou od sebe výpo£etn¥ nerozli²itelné z de nice. D·kaz v¥ty by vyºadoval komplikovaný detailní d·kaz tohoto tvrzení. Dále je nutno dokázat, ºe pokud existuje d·kaz s nulovou znalostí pro n¥jaký
NP-úplný
jazyk, existuje pro v²echny jazyky v
vlastnost nulové vlastnosti
NP,
ºe tedy redukce zachovává
