58
VERJETNOSTNI MODEL RAČUNANJA	INFORMATICA 1/89
Deskriptorji: RAČUNANJE, VERJETNOSTNI MODEL,	Janez Žerovnik
ALGORITMI HEVRISTIČNI	Inštitut za matematiko, fiziko in mehaniko, Ljubljana
POVZETEK: V preglednem članku predstavimo verjetnostni model ratunaqja in podamo delokijo nekaterih razredov časovne zahtevnosti verjetnostnih algoritmov. V začetnih razdelkih vpeljemo klasični (deterministični) model računanja In ponovimo mane definicije iz teorije časovne lahtevnosti algoritmov.
ABSTRACT: A Probabilistic Model of Computation In article a survey of a probabilistic model of computation is given. Some elanes of probabilistic algorithms are defined. Preliminary sections give definition oi classical (deterministic) model of computation and introduction to the theory of time complexity of computation.
1. UVOD
V članku bomo vpeljali nekatere pojme in definicije iz teorije časovne zahtevnosti algoritmov. V slovenščini s tega področja poznamo dve deli [PisaS3, PePi82| in prevod [AhU186|, tuj» literatura pa je precej bolj bogatv Samo problemu trgovskega potnika na primer je posvečena cela knjiga |LLRS86|. Ze klasična Je knjiga Gareya in Johnsona [GaJo79|, mi pa bomo zaradi novejših definicij nekaterih razredov slučajnih algoritmov sledili knjigi [Melh84|, oprli pa se bomo še na [HoU179] in [G11I77].
V zadnjem desetletju In pol so razred NP-polnlh odločitvenih problemov veliko raziskovali. Vprašanje, ali je razred P enak razredu NP je verjetno eden najpomembnejših odprtih problemov teoretičnega računalništva. Teoretično računalništvo tu imenujemo vedo, ki jo nekateri imenujejo tudi informatika (Informatique), kibernetika uporabna matematika (Prikladnaja matematika) ali 'algoritmika' (algorithmics) [Knut81]. Ce bi za katerikoli NP-poln problem uspeli pokazati, da je v P, bi sledilo P=NP.
Ker je veliko praktičnih problemov NP^polnlh, si v praksi pomagamo do delnih rešitev na različne načine. Aprokslmativnl algoritmi na primer so taki algoritmi, ki v polinomskem času najdejo rešitev, ki je 'dovolj blizu' optimalne refitve. Deterministični hevrističnl * algoritmi imajo pogosto lepo lastnost, da najdejo dobre refitve na neki podmnotici problemske domene. Običajno Imajo taki algoritmi 'Ahilove pete': obstajajo primeri, na katerih se algoritem obnaia zelo slabo. Avtorji algoritmov običajno te sami navajajo primere, ki so neugodni za algoritem [WePo67,DuBr81|. Pri slučajnih hevristlčnlh algoritmih
* Splošno privzete definicije hevrističnega algoritma ni |Tros83|. Po Verbinčevem Slovarju tujk je hevristlka: 'nauk o metodah raziskovanja (z uporabljanjem še nedokazanih metod, hipotez, itd.)'. Za našo rabo naj hevristični algoritem pomeni postopek, ki ga uporabljamo, čeprav nimamo dokaza, da so njegove rešitve vedno točne (optimalne). Vemo pa, da na primer velja, da je točen na neki podmnotici problemske domene ali da točno rešuje nek 'podoben' problem ali kakšen podoben delni rezultat.
nekatere korakenaredimo slučajno. S tem se včasih izognemo 'Ahilovim petam' na račun nekaj večje časovne zahtevnosti.
Eden od intuitivno najlatje razumljivih NP-polnih problemov je problem barvanja točk grafa. Ker je sestavek nekoliko predelano poglavje avtorjeve magisterske naloge 'Verjetnostni algoritem ta barvanje točk grafa', je tudi tu najpogosteje obravnavani primer ravno problem barvanja točk grafa. Grtf je kombinatorični objekt, ki ga sestavlja ta mnotica točk V in mnotica E, v kateri so pari točk. Elementom mnotice E pravimo povatvc. Točki, ki sta povezani i povezavo, sta »oteinji Btrvanjt (točk grafa) je prireditev barv točkam grafa. Za barve običajno vzamemo kar naravna števila. Barvanje Je dobo, če je vjik par sosednjih točk pobarvan z različnima barvama. Formalno to zapišemo na primer takole: h : V -* N Je dobro barvanje *=» («, v) € E => 6{«) / b(v). Odločitveni problem barvanja grafa lahko zdaj zastavimo takole: Ali ca dani graf G in mnolico barv {1, —, i} obstaja dobro barvanje? Ce tako barvanje obstaja, rečemo, da je G k-pohrdjiv. Pogosto je zanimiva optimizacijska varianta problema: Poišči minimalni k, da je G še t-pobarvljivt Ta minimalni k Imenujemo kremttilne Hevtio grafa G. V nadaljevanju bomo predpostavljali, da bralec pozna osnovne pojme teorije grafov, kot so vpeljani na primer v [BaPi86] ali [CvMi77].
Problem barvanja grafa je zanimiv tudi iz zgodovinskih razlogov. Problem štirih barv je bil skoraj sto let velika uganka, ob kateri se je razvijala teorija grafov. Problem si je prvi zastavil leta 1852 londonski študent Francis Guthrie, ko je barval zemljevid angleških grofij. Domneval je, da je mogoče vsak zemljevid pobarvati s štirimi barvami, seveda tako, da ozemlja, ki mejijo, niso pobarvana z isto barvo. Pri tem ozemlja, ki se dotikajo samo v končno mnogo točkah ne štejemo za sosednja. Problem običajno zastavimo v nekoliko drugačni obliki. Namesto ozemelj barvamo točke (lahko si mislimo, da so to glavna mesta), povezani pa sta točki, M sta v sosednjih drtavah. Problem »e potem glasi: ali je mogoče točke vsakega planarnega grafa pobarvati s štirimi barvami (tako da pobarvamo poljubni povezani točki z različnima barvama)? Francisov
59
brat Frederic je problem predstavil profesorju Augustu de Morganu. SirSe znan je problem postal leta 1878, ko je Arthur Cayley na srečanju Londonske matematične drulbe (London Math. Society) vpraJal, ali je problem le reSen.
Prvi »e je reievanja problema resno lotil A.B.Kempe, ki je leta 1879 objavil dokaz, da Štiri barve zadoičajo. Deset let kasneje je P. J.Heawood odkril napako v Kempejevem dokazu, ki pa so jo mnogi imeli bolj ta tehnično pomanjkljivost kot pa za resno napako. Ko pa so leta minevala in nikomur ni uspelo popraviti dokaza, je postalo jasno, da problem ni od muh. Leta 1976 sta Kenneth Appel in Wolfgang Haken objavila, da sta dokazala izrek o Štirih barvah. Ideja dokaza Je v bistvu enaka Kempejevl, le Število posebnih primerov, ki jih Je bilo potrebno pregledati, je precej večje (okoli 1500 namesto 51). Obsežnost Je tudi glavna hiba dokaza, saj je za pregled (okoli 600 strani) dolgega dokaza potrebno ogromno časa, tudi če za nekatera rutinska opravila uporabimo računalnik, kot sta to storila avtorja dokaza |WoWi78,ApHa86].
2. Primer NP-polnega problema
Za motivacijo si v tem razdelku Se pred formalnimi definicijami oglejmo problem klike (skupka). Zastavimo ga takole: Dan je (neusmeijen) graf G = (V, E) in naravno število k. Ali v G obstaja podgraf, ki je izomorfen polnemu grafu Ki? Obstaja enostaven, toda neučinkovit algoritem za reievanje tega problema. Pregledamo vse podgrafe v G, ki so inducirani z množicami točk kardinalnosti k. Za vsak tak podgraf pa preverimo, če je poln. Med n točkami lahko izberemo k točk na (J) načinov. V primeru i = n/2 torej naj algoritem preveri (.",) > 2*/(n+l) podmnotic. Preverjanje, ali je graf poln, je enostavno in hitro: za vsako od n(n-1)/2 povezav pogledamo, ali je v induciranem grafu. NaS naivni algoritem torej zahteva čas, ki je eksponentna funkcija Števila točk danega grafa. Preden trdimo, da je to neučinkovito, povejmo, kaj mislimo z velikostjo problema. Predpostavljali bomo, da so kombinatorični objekti (grafi, množice, cela Števila,...) podani v 'normalni obliki' s končno abecedo. Tako bo na primer graf z n točkami zakodiran v obliki zaporedja nJ bitov, v katerem so zložene vrstice matrike sosednosti. Cela Števila zapiiemo v binarnem zapisu in mnoiice z zaporedjem elementov v nekakšnem redu. Primer problema klike na grafu i n točkami je potem zaporedje bitov dolžine m := nJ + logfn/2) + 1, če spet zaradi enostavnosti vzamemo primer k = n/2. NaS naivni algoritem torej razpoznava jezik CLIQUE = {tov; t»,« € {0,1}' in |ui| = nJ za neki n in graf G c matriko sosednosti w ima kliko velikosti k, kjer je v binarni zapis Števila k} v času 0(2v""), kjer je m velikost problema (dolžina vhoda). Algoritma, ki bi bil bistveno boljSi od opisanega, ne poznamo. Ker je problem klike NP-poln, je zelo malo verjetno, da tak algoritem sploh obstsja. To bi namreč pomenilo, da obstajajo učinkoviti (polinomskl, kot bomo kasneje definirali) algoritmi za vse NP-polne probleme, na primer za problem trgovskega potnika In problem izpolnjivosti. SploSno je privzeta hipoteza 'P^NP', da takih algoritmov ni. Dokaz ali protidokaz te hipoteze je verjetno najbolj znan odprt problem teoretičnega računalništva.
še malo se zadrfimo pri problemu klike. Podmnofic kardinalnosti k med n točkami je (J), torej obstaja zelo veliko kandidatov za kliko. Po drugi strani je zelo lahko preveriti, ali je dani kandidat klika ali ne. Edina znana pot pa je pregledati vse kandidate.
Ce bi imeli na razpolago nedeterministični ukaz CHOICE, bi lahko problem reSili učinkoviteje. Ukaz bi bil na primer oblike
CHOICE Nation, Natlovj
Z nedeterminizmom je mišljeno, da izbira nadaljevala nima nobene vnaprej določene verjetnosti. Ukaz CHOICE pač pomeni, da se algoritem lahko nadaljnje na naslovu Naslovi ali pa na naslovu Nailovi. Algoritme z ukazom CHOICE imenujemo nedeterministične. Tak algoritem razpozna vhodno zaporedje, {e obstaja vsaj ena izvedba algoritma, ki razpozna vhod.
Časovna zahtevnost nedeterminističnega algoritma je čas najkrajše izvedbe, ki je razpoznala vhod.
Za primer poglejmo, kako bi problem klike reSili z nedeterminističnim algoritmom. Nedeterminizem bomo uporabili pri generiranju kandidatov za kliko. Algoritem je sestavljen iz treh faz. Najprej pregledamo vhodno zaporedje bitov in preverimo, ali je vprašanje dobro postavljeno. Ce vhod ni oblike vv in |t«| ni kvadrat naravnega Števila, ga zavrnemo, sicer pa izračunamo n = yftrf in k. Z |t»| smo označili dolžino zaporedja znakov (v tem primeru znakov iz abecede {0,1}) m. Časovno zahtevnost prve faze lahko ocenimo z 0(n*). V drugi fazi nedeterminlstično izberemo podmnožico V kardinalnosti t, tako da zgeneriramo zaporedje n bitov z natanko k enicami. To naredimo takole:
for t := 1 to n
do CHOICE mi, nn m, : A[t\ := 0; m, : := 1; * := k - 1;
od
U k / 0 then »vrni;
Uspeina izvedba gornjega dela algoritma generira eno od (J) podmnolic V. Potrebni čas je očitno reda 0(n). V tretji fazi preverimo, ali je izbrana podmnožica klika. Tudi to lahko storimo hitro, vsaj 0(n4). Opisani algoritem potrebuje čas 0(n4) = 0(tti3), kjer je m dolžina vhodnega zaporedja. Podani algoritem res razpoznava jezik CLIQUE: Ce G ne vsebuje klike velikosti l, potem v drugi fazi zgenerirana podmnotica gotovo ni klika, torej izvedbe, ki bi sprejela vhod, ni. Ce pa graf G ima kliko velikosti k, potem v eni od mogočih izvedb algoritem zgenerira prav to kliko. Ta izvedba seveda sprejme vhod.
Videli smo, da lahko problem klike reiimo v polinomskem času z nedeterminističnim algoritmom. Razred problemov, ki so rešljivi v polinomskem času z nedeterminističnim algoritmom označimo z NP. S P pa označimo razred problemov, reSljivih v polinomskem času z determinističnim algoritmom. Med NP problemi posebej obstajajo problemi, na katere je mogoče prevesti (v polinomskem času) vsak drug NP problem. To so NP-polni problemi. Cook je v članku [Cook7l| je pokazal, da je problem izpolnjivosti {SAT) NP-poln. S polinomskim prevajanjem pa je bilo od tedaj za veliko problemov dokazano, da so tudi NP-polni, med drugimi tudi problem klike in problem barvanja točk grafa [Karp72|. Obsežni seznami NP-polnih problemov so v knjigah, na primer v |GaJo79|.
Za strogo obravnavo opisanih problemov potrebujemo formalno definiran model računanja, ki ga podajamo v naslednjem razdelku.
i
3. Turingov stroj
V tem razdelku bomo definirali model računanja s pomočjo katerega bomo lahko strogo definirali časovno zahtevnost algorit mov In razdelili proble me glede na težavnost. Model računanja, ki ga običajno izberemo, je Turingov stroj (TS), saj kljub enostavnosti ni nič SibkejSi od katerega koli doslej zgrajenega 'superračunalnika'. Vsi znani modeli so namreč polinomsko prevedljivi na model TS, kar pomeni, da so v Bmislu teorije, ki nas tu zanima, ekvivalentni. Ce drfl Churcheva teza, pa to velja za vse mogoče modele računanja! NaSa definicija se rahlo razlikuje od tistih v [Pisa83j in [PePi82|, vendar nas to ne moti zaradi znane ekvivalentnosti modelov računanja [PePi82, GaJo79, Melh84, AhHU76, H0UI86].
Turingov stroj ima dve enoti: kontrolno in spominsko. Spomin je v desno stran neomejen trak, ki je razdeljen na kvadratke, v katerega je mogoče zapisati en znak končne abecede, ki jo uporablja konkretni Turingov stroj. Kontrolna enota ima končno mnogo stanj in lahko naenkrat dosega en znak (kvadratek) na traku. Turingov stroj programiramo s tabelo, v kateri za
60
vsaJco stanje ¡n vsak znak abecede (v trenutno vidnem kvadratku) določimo mnofico motnih operacij. Ce je mnotlca prazna, se TS ustavi. Ce je Turingov «troj determinističen Ima mnotlca motnih operacij v vsakem primeru največ en element, obnaJanje determinističnega Turingovegastroja je s tabelo in vhodnim podatkom torej natanko določeno. TS v eni operaciji lahko naredi troje: lahko zapUe znak na trenutno vidni kvadratek traku, lahko premakne 'oko' v levo ali desno in lahko preide v novo stanje.
TS potenemo tako, da zapiJemo vhodno zaporedje znakov na prvih n kvadratkov, postavimo 'oko' na prvi (skrajnje levi) kvadratek traku in postavimo TS v (vedno Isto) začetno stanje. Vsi drugi kvadratki na traku so v začetku prasni, vsebujejo torej posebni znak abecede B. TS Izvaja operacije, dokler ne naleti na par (znak, stanje) za katerega v tabeli nima nobene operacije In se ustavi. Rezultat računanja je nepraznl del traku. Na ta način lahko TS uporabimo za računanje funkcij. Pogosteje pa rabimo TS za razpoznavanje jezikov. TS razpoznavajezik, te izračuna njegovo karakteristično funkcijo. Da se izognemo (nepotrebnemu) brisanju traku pa se dogovorimo, da odlikujemo nekaj stanj in rečemo: če se Turingov stroj ustavi v katerem od teh stanj, je razpoznal vhod za element jezika. Obe definiciji sta ekvivalentni, druga pa je primernejša za obravnavo nedeterminizma.
1 .DEFINICIJA: Turingov stroj (TS) Je sedmerk» Af = (9, E, T, 6,qo,B, F), kjer Je Q končna mnotica stanj T tračna abeceda B 6 T prazen simbol
E, E C T \ (B) mnofica vhodnih simbolov
i prehodna funkcija Q x T —► Q x T x {L, R), ki ni nitfno definirana na vsej mnoiici Q x T qe e Q začetno stanje F CQ mnofica končnih stanj
Zaradi nedvoumnosti privzamemo, da sta r in Q dlsjunktni množici simbolov. Trenutno stanje Turingovega stroja opisuje lon/ijuranja, to je niz oblike otijoj € T* X (J X T', kjer je q trenutno stanje TS, ajaj je zapis na traku, TS pa vidi prvi znak niza ori. Ce je a3 = t prazen niz, potem TS po dogovoru vidi prazen znak B.
Deflninjmo korak TS. Bodi XiXi...X{-iqXi...X» konfiguracija. Naj bo i(j, = (p, Y, L), kjer v primeru i-1 = n vzamemo Xi = B. Če Je»' = 1, potem naslednja konfiguracija ni definirana, saj stroj ne sme 'pasti' čez levi rob traku. Ce je i > 1 potem zapiiemo
X\Xt .. gXi. ..Xn h X\Xt. ..Xt-ipXi-iYXi+\,. ,Xt
Ce se nam na koncu zapisa konfiguracije pojavijo prazni simboli, jih po dogovoru zbrilemo.
Podobno definiramo korak, če je i(j,Xi) = (p, K, R).
X\Xi. ..Xi~ ¡jXi ...Xm I- X\Xj ...Xi~iYpXi+i ...X„
V primeru »' - 1 = n je niz ... X» je zapis konfiguracije po koraku daljii od zapisa prejflnje konfiguracije.
Konfiguracija C = X\Xt...Xi-iqXt...X% je nrf«t>i(tmti«, če velja i(?,A() = i. Konfiguracija Je iprejcmtjol«, če Je { e F. Konfiguracija je tščetnt pri podatku i = Aj, Jf»,..., X», če je j = fo, in i = 1.
Itrtivn pri podatku z € P je zaporedje konfiguracij Co,Ci,...,Ct, za katere velja Ct 1- za 0 < t < k. Izračun »e nitivi, če je končna konfiguracija C» ustavitvena. Izračun je iprejtm*jo&, če Je njegova končna konfiguracija Ct sprejemajoča. Brez škode za splolnost lahko privzamemo, da se vsak sprejemajoč račun ustavi.
2.DEFINICIJA:	Ncicttrminuiilni Turingov ttroj (NTS) definiramo en&ko kot TS, le prehodna funkcija i ima več mogočih vrednosti. Točneje {: Q X T — 2Qxr(R,L)
V	posebnem primera, ko Število elementov v sliki i ni nikoli vefje od 1, dobimo prej definirani (deterministični) TS.
3.DEFINICIJA:	Bodi M = (Z, T, i, i") TS:
a)	L(M) = (i € T'; obstaja sprejemajoč izračun TS M t vhodom i) je jezik, ki ga razpoznava M
b)	Bodi M determinističen in loltlcn, torej naj J« M ustavi pri poljubnem vhodnem nizu x € P. Potem M računa funkcijo /v r* -> T, te je ta vsak i € T' vsebina traku ob ustavitvi enaka fu(z).
c)(Casovnazahtevnost	Tm TS M)
Tv(n) = max,€TM«|=»{*;* i" doliinit iimčuna, ki te uitsvl pri vhodu
4.DEFIN1CIJA:	(Razreda P in NP)
P = {t; i C T'za neko končno abecedo T in obstaja deterministični TS M in polinom p, da je L-L[M) in T«(n) < p(n) za vsak ts} NP = [L;L C T'za nejto končno abecedo T in obst^/a nedetermini/tični TS Min polinom p, daje L = L{M) in T»/(n) < pjn) za vtt n)
V	nekaterih virih |GaJo79,AhHU76,Melh84] je tasovna zahtevnost NTS definirana nekoliko drugače:
6.DEFINICIJA:
Tu{n) = max»gi,(v),|i|=m min{Jt; k je do/fina sprejemnega izračuna pri vhodu i)
če je M nedeterminlstičen, In
Tw(n) = maxjer.,|,|=, (k; k je doliina izračuna, ki se ustavi pri vhodu
*}
če je M determinističen.
Tv(n) = oo, če obstaja z € P, |i| = n tak, da se M ne ustavi pri vhodu
z.
Ker Je stara definicija Tu{N) v primeru NTS strotja od nove, bi se lahko zgodilo, da bi se razred NP zdaj zajemal manj jezikov. Z NPi za hip označimo razred jezikov, ki je definiran tako, da v definiciji 4. uporabimo novo definicijo TU(N). Očitno je
NPi 2 NP Na srečo pa ve(ja tudi obratno, torej:
6.IZREK: NP, = NP
DOKAZ: Dokazati moramo NPi C NP.
Naj bo L € NPj. Torej obstaja NTS M s pollnomsko časovno zahtevnostjo v smislu definicije 6, ki razpoznava L. Konstruirali bomo NTS N, ki bo razpoznaval Isti Jezik In bo imel pollnomsko čatovno zahtevnost v imlslu definicije 3. Bodi p(n) = Ty(n) časovna zahtevnost NTS M, kjer Je p neki polinom.
TS N naj deluje takole:
-	simulira delovanje NTS M in Iteje korake
-	ko doseie Itevilo korakov p(n), se N ustavi
-	če je v tem času M razpoznal vhod, ga razpozna tudi N, v vseh drugih primerih pa N odgovori NE.
N očitno razpoznava natanko L, saj po predpostavki za vsak element iz L obstaja sprejemajoč izračun z ne več kot p(n) koraki.
Ker simulacija gre v polinomskem času, je časovna zahtevnost NTS S
61
očitno polinomska v smislu definicije 5.
Q.E.D.
Ker je vsa* deterministični TS hkrati nedeterministični TS Je očitno P C NP
Priili smo do znanega odprtega problema: ali morda velja P=NP? Prevladuje sploino prepričanje (ki seveda ne dokazuje ničesar), da P=NP ne veljv Tuk»j navajamo dva 'zdravorazumska' argumenta:
a)	Obstajajo problemi (takoimenovani NP-polnl, definicija pride kasneje), na primer problem izpolnjivosti [SAT), r.a katerega velja
P = NP <=> SAT € P
Problemov s to lastnostjo je Je veliko, prihajajo p» z različnih področij. Iz teorije grafov omenimo problem klike in problem barvanja točk grafa. Razvpiti problem trgovskega potnika je samo eden izmed težkih (beri NP-polnlh) transportnih problemov v operacijskih raziskavah. Mnogo dela mnogih raziskovalcev je bilo brez uspeha, ko so iskali učinkovite (polinomske) algoritme za te probleme. Se ved,
b)	za mnoge algoritme, ki so jih predlagali, se je izkazalo, da imajo več kot polinomsko časovno zahtevnost.
Za konec razdelka navedimo te izrek, ki primetja deterministično in nedetermlnistično časovno zahtevnost. Enostavna simulacija da za eksponentni red večjo časovno zahtevnost pri simulaciji nedeterminističnega TS z determinističnim. Boljie simulacije ne poznamo. Ce velja P £ NP potem je to tudi najboljie, kar lahko dosetemo.
7.DEFINIC1JA: Funkcija T : N N je lotom» funkcij*, Se obstaja deterministični TS, ki se ustavi po natanko T(n) korakih pri vsakem vhodu doltine n.
Nekatere običajne funkcije so tudi časovne funkcije, na primer T(n) = n, T[N) = npog n), T(«) = n', T(») = 2V
8.IZREK: (Simulacija nedeterminističnega TS z determinističnim) Bodi T(n) časovna funkcija, L C T* jezik in N nedetermlnlstični TS, ki sprejema L v času TN(n) = 0(T(n)). Potem obstaja deterministični TS M z L(M) = L in 7w(n) = 0(cT<')) za neko konstanto c.
DOKAZ: Za vsak i E i obstaja izračun doltine < 7V(|x|), ki sprejme z. Bodi k = m&x{cord(i(i,a)); t stanje TS N in o e T}. Potem ima TS N na vsakem koraku največ k različnih mogočih operacij. Torej je največ *r»<l*D različnih izračunov, ki se ustavijo, doliine < Tn(|x|) pri vhodu r. Spomnimo se, da je z € L natanko tedaj, ko je vsaj eden od izračunov, ki se ustavijo, sprejemajoč. Uporabimo to pri simulaciji) Izberimo tak m, da bo IV (n) < mf(n) za vsak ». Poglejmo cela itevila od 0 do pri osnovi k. Vsaka od mogočih izvedb TS N je zakodirana kot eno od teh itevil na naslednji način: i-ta cifra v jfc-adičnem zapisu itevila določa operacijo na i-tem koraku izvedbe. (Nekatera Itevila ne predstavljajo motne izvedbe, vendv nas to ne moti.) Enostavno je videti, da je vsako konkretno izvedbo TS N potrebno največ p(mT(|x|)) korakov, za neki polinom p. (Res, dodatno moramo na vsakem koraku poiskati naslednjo cifro »kodirane izvedbe, za to se moramo največ dvakrat zapeljati čez trak.) Torej celotna simulacija zahteva čas p(mT(|i|))k",r<W> = 0(cr<W>) za neko konstanto c.
Q.E.D.
4. Problemi, j etiki in optimizacijski problemi
Razreda P in NP smo definirali za jezike. Praktični problemi pa običajno niso
formulirani v obliki problema razpoznavanja nekega jezika. V tem razdelku
bomo pokazali ivezo med optimlzacijskimi problemi in njihovimi odločitvenimi inačicami.
Za primer si poglejmo odločitveni problem barvanja točk grafa in ustrezni optimizacijski problem.
Problem: Optimizacijski problem barvanja točk grafa Vhod: Graf G
Iitaod: Dobro barvanje grafa G i x(G) barvami Optimizacijski problem barvanja točk grafa očitno ni jezik, pač pa zahteva ir.račun neke transformacije ii matrike n x n bitov v taporedje n itevil 6 {1,2, ...,x(G)} (ki označujejo barve). Pripadajoči odločitveni problem je Problem: Odločitveni problem pobarvljivosti grafa (k-COL) Vhod: Graf G in celo Itevilo k
Vpraianje: Ali obstaja dobro barvanje grafa G z največ k barvami? Odločitvenemu problemu je mogoče na naraven način prirediti jezik. To je mnotica vseh primerov problema (G, k) ali točneje zapisano m, kjer je w koda grafa G in v koda itevila k, it katere je odgovor na dano vpraianje potitiven. ik-coL = {(G, (t); G Je k-pobarvljiv ) Oziroma
£k-COL = { w Je matrika povezav nekega grafa G in v Je binarni lapis nekega celega Itevila k ln graf G Je *-pobarvljlv }
Mimogrede smo privzeli, da je kodiranje nailh problemov 'naravno'. Kot smo omenili te v uvodu poglavja, se dogovorimo, kako bomo kodirali kombinatorične objekte: naravna itevila bomo zapisali binarno, sploine grafe pa z matriko sosednostl. Bistvena je zahteva, da kodlrna shema ne sme umetno znilatl zahtevnosti problema. Ce bi na primer naravna itevila zapisali
unarno (n = 111 ...lj, bi namesto vhoda doliine O(logn) imeli vhod doltine ■
O(n). Tako bi eksponentni algoritem navidez postal polinomski! Podrobneje so rahteve 'naravnega1 kodiranje opisane na primer v |PeP182).
Odločitvenemu problemu smo priredili jezik, torej se lahko vpraiamo, ali je problem v P. V nadaljevanju bomo pokazali, da bi v tem primeru optimizacijski problem lahko reiill v pollnomskem času. Torej lahko tudi za optimizacijski problem rečemo, daje polinomski, če je njegov pripadajoči odločitveni problem v razredu P.
Za začetek poglejmo karakteristično lastnost razreda NP. 9.IZREK:
NP = {I; L C £• za neJro končno abecedo £ in obstaja polinom p in polinonuko izračunov predikat Q(x,y) C t' x E* , da za vsak ieE' ve(ja:
z 6 L <=> 3» € V : |y| < p(|x|) in <?(«,»)} Niz jr Imenujemo certifikat.
DOKAZ: a) Bodi p polinom in Q polinomsko izračunljiv predikat. Torej obstaja deterministični TS M, ki izračuna Q(x, y) v času j(x, y) ta neki polinom j. Naslednji nedeterministični algoritem sprejme L.
(1)	Ob vhodu x nedetermlnistično zgeneriraj zaporedje i € E', |y| < p(|x|)
(2)	Razpoznaj i, če je res <J(r,j/) (izračunano z Ki) Nedeterministični algoritem v delu (1) je podoben algoritmu, s katerim
smo v prvem razdelku reievali problem klike. Kot smo se prepričali le tam, je algoritem polinomski na nedeterminističnem TS, itevilo korakov pa je omejeno s p(|t|). Časovna zahtevnost drugem delu algoritma je omejena s polinomom f, ki je odvisen od doltine vhoda |x| in doltine |y|, ki pa je spet omejena s polinomom p(|x|). Torej je L € NP.
b) Bodi I £ NP i C £'. N naj bo nedeterministični TS, ki razpoznava L v času, omejenem s polinomom p. Kot v dokazu prevedljivosti nedeterminističnega TS na deterministični TS (Izrek 8) naj bo k največje Itevilo različnih operacij, kijih na enem koraku lahko izbere N. V dokazu omenjenega
62
izreka smo ugotovili, da lahko t zaporedjem cifer v i-adičnem številskem zapisu natanko določimo (zakodiramo) vaako od motnih izvedb NTS pri vhodu z. Brez škode za spiošnost vzemimo, da je |£| > k. Definiramo
y) = 'y je koda aprejemajočega izračuna NTS N pri vhodu z1
Q je (po definiciji razreda NP) izračunljiv v polinomskem (asu in L = {«;3»W<p(M).n g(x,»)}
Q.E.D.
Izrek daje motnost alternativne definicije razreda NP, ki ima vaaj eno prednost. S tako definicijo se izognemo razlaganju fenomena nedeterminizma, tu vse delo opravi en eksistenčni kvantlfikator!
10.definicija:	Sfinimiiteijiki problem je podan s polinomsko izr&čunljivim predikatom Q C E* x E* in polinomsko izračunljivo namensko funkcijo c : E* x E* —► N. Ce velja Q(x,y), potem je y ioptutnt rešitev problema pri vhodu x s 'stroškom' c(x, Ce velja Q(x, y) in c(z, y) < c(x,
za vsak if za katerega velja <J(x, p*), potem je y optimalna rešitev za z. Minimizacijski problem je polinom»ko omejen, če obstaja polinom p, tako da iz
<?(*,») sledi W<P(M).
V tem delu bomo obravnavali lamo polinomsko omejene probleme. Podobno kot minimiz&cijake bi lahko definirali maksimizacljske optlmizacijske probleme. V primeru optimizacijskega problema barvanja točk grafa je <J(x, izpolnjen, če je z koda grafa, y pa koda dobrega barvanja. e(x, jr) je število barv, uporabljeno v barvanju, ki ga kodira y.
11.DEFINICIJA:	Bodi (Q,c) polinomsko omejen minimizacijski problem. Definiramo štiri verzije problema:
a)	Problem: (Q,c)-odločitveni problem Vhod: z €E\ celo število C
Vpralanje: Ali obstaja y, da velja Q(z,y) in e(z, y) < Ct
b)	Problem: (Q,c)-optimizacijaki problem Vhod: z € E'
Iihod: Optimalna rešitev opt»ol(x) e E' za z
c)	Problem: (Q,c)-problem optimalne vrednosti Vhod: z e E«
Izhod: optml(x) = e(z, op<ioi(x))
d)	Problem: (Q,c)-problem C-retttve Vhod: z 6 E', celo število C
Ishod: y = wiine»«(C), da velja 0(x,y) in c(t, y) < G, če tak y obstaja.
Za primer barvanja točk grafa smo prvi dve verziji problema ie videli. Problem iskanja optimalne vrednosti v primeru barvanja točk grafa pomeni izračun kromatlčnega števila x(G), problem C-rešitve pa formuliramo takole: pri danem C poišči dobro C-barvanje, če (seveda) obstaja.
Primerjajmo časovno zahtevnost štirih verzij problema. Očitno problem razpoznavanja ni tetji od problema C-rešitve in problema optimalne vrednosti, ta dva pa nista teijaod optimizacijskega problema. Ali bolj nazorno:
problem
problem ^ C-rešitve	^ op^^acijski
razpoznavanja ^ probtem ^^ ^ Problem vrednosti
Natančneje formuliramo pravkar povedano z naslednjimi trditvami:
12.LEMA:	Bodi (Q,c) polinomsko omejen optimizacijski problem. Potem velja:
a)	Ce Je funkcija opttol : E* —> E* izračunljlva v polinomskem času, potem isto velja za funkciji optval: E* —• E* In witncu : E* —> E' .
b)	C« je vsaj ena od funkcij un'tne«« in opt val izračunljiva v polinomskem času, potem je
L(Q.c) := {(z,C);z € E\C 6 Mn optval < C) € P
DOKAZ: Očitno iz prej povedanega.
Manj očitno Je, da velja tudi obrat zadnje leme. V splošnem znamo dokazati nekoliko šibkejšo obratno trditev. Primer, ki ga v splošnem ne znamo dokazati, pa bomo dokazali za poseben primer barvanja točk grafa.
13.LEMA:	Bodi (Q,c) polinomsko omejen optimizacljsk! problem.
a)	Ce sta funkciji milne«« in optval itračunljivi v polinomskem času, potem isto velja za optiol.
b)	Ce je problem razpoznavanja v razredu P in za neki polinom j velja optuol(z) <	za vse z, potem je funkcija optval Itračunljiv» v polinomskem času.
DOKAZ:
a)	Trivialno, saj za vsak z velja opt»o/(z) = t»tfnei»(z, opfrai(r)).
b)	Za izračun optimalne rešitve optval bomo uporabili binarno iskanje med vrednostmi {l,...,2»it*D}. Poglejmo naslednji algoritem:
low := 0;
high := 1;
while z nima rešitve < high do high := 2 • high;
while high - lote > 1
do middle := tr»nc((M'jfi + low)/2) if x ima rešitev < middle then high := middle else low := middle; od
optval(x) := low,
Ker je problem po predpostavki polinomsko omejen, vemo, da je rešitev omejena z 2*d*l>, kjer je q neki polinom. Prva while zanka torej v polinomskem številu korakov določi zgornjo mejo rešitve.
Hitro vidimo, da je low < optval(z) < high invarianta do zanke. Torej gornji algoritem pravilno izračuna vrednost optval[z) v lojj(2,"*l)) = j(|z|) ponovitvah zanke. Ce v drugi while zanki uporabimo polinomski algoritem za razpoznavanje, ki po predpostavki obstaja, smo torej res našli polinomski algoritem za izračun optimalne vrednosti optral(i).
Q.E.D.
Primerjavo med problemom C-vrednosti in problemom razpoznavanja naredimo za konkretni primer barvanja. V knjigi [Melh84| najdemo dokaza za problem trgovskega potnika in za izpolnjivost, pa tudi trditev, da podobni dokazi, v katerih uporabimo tehniko redukcije problema na manjši problem iste vrste, obstajajo tudi za mnoge druge NP-polne probleme.
14.LEMA:	Ce je odločitveni problem C-barvanja v P potem obstaja algoritem, ki v polinomskem času poišče C-barvanje.
63
DOKAZ: Idejo it |PePi82| zapilimo v obliki algoritmi:
if not C - COL(G) then (»barvanja ni*)
eUc
for c := C downto 2 do begln
izberi poljubno točko u 6 V(C);
pobarvaj u z barvo c,
for ali točke v €	ki niso sosede u-ja do
lf not c - COHV(CT), E(G') U («, ti)) then begln (*točki sta neodvisni!*) pobarvaj v z barvo <r, identificiraj u in t; v (T1; end; GT := G' \{u}
end
preostale točke v C pobarvaj z barvo 1
Identifikacijo dveh točk grafa očitno lahko naredimo v linearnem času (potrebno je namesto dveh vrstic (stolpcev) enega pobrisati, v drugega pa vpisati konjunkcljo vrstic (stolpcev)), zato je gornji algoritem pollnomski, seveda pri predpostavki, da je algoritem, ki odloči, ali je graf c-pobarvljiv, polinomski.
Q.E.D
S. Polinomsko prevajanje In NP-polnl problemi
Prevajanje problemov je uporabna tehnika ta ugotavljanje 'telavnosti'
problemov. (Primer smo videli v prejinjem razdelku.)
15.DEFINICIJA: a) Naj bosta E in T končni abecedi. Preslikava/: E* -. T' je polinomika trantformaet/o, če lahko / izračunamo v polinomskem čuu na determinističnem TS.
b)	Bodita L\ C E* In Lj C T* jezika. L\ je polinom/te prevedljiv na Lj, oznaka Li<x Lj, če obstaja polinomska transformacija /, tako da je
z e ¿i <=> f(z) e l3
za vse z € E'.
c)	Jezik L je NP-poln, če velja
1)	i€NP
2)	L' <x L, za vse L' e NP
Pomembnost definicije pojasni naslednji
16JZREK: Bodi Lo NP-poln. Potem
a)	L0 e P <=► P = NP
b)	če je ¿o « ¿i in L\ 6 NP, potem Je L i NP-poln
DOKAZ: a) Ce je P=NP potem je gotovo L0 € P. Dokazati moramo le drugo smer ekvivalence. Bodi lo £ P in L £ NP poljuben. Ker je Lo G P, obstaja deterministični TS M, ki sprejme L o v čuu omejenem z nekim polinomom p. Ker je Lo NP-poln in L e P, velja L <x Lo- Torej obstaja polinomsko izračunljiva preslikava /, tako da je L = /-1 (Lo). Bodi N deterministični TS, ki izračunava / v času, omejenem s polinomom j. Iz TS M in N konstruirajmo nov TS A, ki bo razpoznaval L takole:
(1)	Izračunaj /(») v času ?(|x|) s TS N.
(2)	Premakni glavo ('oko') na prvi simbol f(z) v času |/(z)|
(3)	Razpoznaj /(z) uporabljajoč M v času p(|/(z)|). Ce je f(z) G Lo, potem sprejmi z, sicer ga zavrni.
Gornji algoritem očitno razpoznava L. Potreben čas je ?(|x|) + |/(x)| + p(|/(*)|) < r(lJl) nel" polinom r. Zadnja neenakost je posledica dejstva, da je |/(z)| < |x| + ?(|x|), saj lahko TS v enem koraku porabi največ en nov kvadratek traku.
b) Pokazati moramo, da je L a ¿i za vsak L € NP. Vzemimo poljuben L € NP. Ker je Lo NP-poln, obstaja polinomska transformacija /, da jt L = /~'(Lo). Ker je Lo <x L\ obstaja tudi polinomska transformacija j, tako da je Lo = f-1(Li). Označimo h = g o /. Potem je L = /_1(Lo) = /"'(»"'(^O) = (i°/)~'(£i) = k-1(in). S podobnimi argumenti kot v točki a) pokaietno, daje h polinomska transformacijv
Q.E.D.
NP-polni problemi so torej najtežji med problemi razreda NP. Ce bi bil eden izmed njih relljiv v polinomskem času, potem bi bili vsi reiljivi v polinomskem času in veljalo bi P=NP. Po drugi strani pa velja: iz N/NP sledi, da noben NP-poln problem ni rešljiv v polinomskem času.
Točka b) nam da enostavno tehniko za dokaz NP-polnosti danega problema. Ce telimo pokazati, da je L NP-poln, moramo dokazati L e NP in Lo oc L za nek problem Lo, » katerega le vemo, da Je NP-poln.
Prvi dokaz NP-polnosti nekega problema je naredil Cook v svojem klasičnem članku |Cook71]. Dokazal je, da je problem izpolnjivosti NP-poln. Dokaz tu opuščamo, bralec ga lahko najde v knjigah, na primer v |GaJo79| ali |M<4h84), v sloveničini pa v |PeP'i82). Ko tak dokaz imamo, lahko relativno enostavno poka/emo NP-polnost drugih problemov, kot je prvi storil Karp |Karp72|. Seznam NP-polnih problemov se od tedaj Siri, zajetne sezname lahko bralec najde v omenjenih knjigah.
Za problem k-COL (odločitveni problem barvanja točk grafa) je dokazal NP-polnost le Karp |Karp72l- Dokaz Je posreden, vmes pokaie NP-polnost problema 3-izpolnjivosti (3-SAT). Dokaz tu opuščamo, bralec ga lahko v sloveničini najde v |Gode83). Pravkar povedano zapijimo v obliki izrekov:
17.IZREK: Problem izpolnjivosti je'NP-poln.
18.IZREK: SAT <x 3-SAT oc k-COL
6. Verjetnostni model računanja
V tem razdelku bomo definirali še nekaj novih razredov časovne zahtevnosti algoritmov. Namesto načrta si poglejmo naslednji diagram:
RP s	NP
p c LVP t £ ^	BPP esC PP c PSPACE
V	.S»	C?
co-RP c	co-NP
Slika 1. Nekateri razredi jezikov kjer je co-C:={r* - L; L € C in T končna abeceda} za vsak razred jezikov
C.
Nove razrede problemov bomo definirali s pomočjo verjetnostnega Turingovega stroja. Verjetnostni Turingov stroj je TS z motnostjo slučajnih odločitev. Tukaj samo omenimo, da s tem računska moč stroja ni nič večja. Mogoče pa je, da se lahko kak problem reši hitreje ali na manjšem prostoru, kot z determinističnim Turingovim strojem.
19.DEFINICIJA: Verjetno*™ TuHniov ttrtj (VTS) je DTS s posebnimi stanji, v katerih sta mogoči dve nadaljevanji, ki sta enako verjetni.
64
Tika definicija VTS je ugodna zaradi enostavnosti. Ker so vse veje enako verjetne, dobimo enostavno porazdelitev motnih rezultatov. Model, v katerem bi dovolili neuravnotežene verjetnosti nadaljevanj, ni nit močnejši od tukaj definiranega [Sch«86j.
V splošnem VTS računa slučajno funkcijo: ta vsak vhod z izračuna VTS rezultat y i verjetnostjo Pr{M(x) = y}.
20.DEFINICIJA:	Delna funkcija, ki jo izračunava VTS hi je definirana z
*„(«) = J»	,čePr{A/(x) = ,}>*
' | nedefinirano ,če takega y ni
21.DEFINICIJA:	Verjetnott napake VTS hi je
eu(z) = i Pr{M(r) / *M(z)} ,ie je *M(z) definirano ' | nedefinirano	.sicer
22.DEFINICIJA:	VTS hi izračunava ¿m z omejeno verjetnostjo napake, če obstaja konstanta« < J, tako da je eu(x) < s za vsak z iz domene ¿v.
23.DEFINICIJA:	(Bhimova) (atoma tMemori VTS M je
I najmanjši n, da je
JV{V(«)-♦*(»)}> l
v manj kot n korakih ,če je t ki (z) definirano
oo	,sicer
7w(n) = nj£cTw(n)
Zadnja definicija je analogna definiciji časovne zahtevnosti NTS kot doltine najkrajšega sprejemajočega izračuna (definicija 5.).
24.DEFINICIJA:	VTS je polinonuka omejen, te obstaja polinom p, tako da se vsak možen izračun vhodov dolžine n ustavi po največ p(n) korakih.
25.DEFINIC1JA:	VTS razpoznava jezik, če izračuna njegovo karakteristično funkcijo.
Ali, drugače zapisano: z G L O Pr{M{x) = 1}>^ in Pr(M(z) = 0}> i
26.DEFINICIJA:
PP = 'razred jezikov, ki jih razpoznavajo polinomsko omejeni VTS' BPP = 'razred jezikov, ki jih razpoznavajo polinomsko omejeni VTS z
omejeno verjetnostjo napake' ZPP (ali LVP) = 'razred jezikov, ki jih razpoznavajo VTS s polinomsko
povprečno časovno zahtevnostjo in z verjetnostjo napake O'
27.IZREK: LVP C BPP C PP C PSPACE
S PSPACE smo označili razred jezikov, ki jih razpoznavajo TS s polinomsko omejeno dolžino uporabljenega traku. Izkaže se, da je vseeno, če vzamemo v definiciji deterministični ali nedetermlnlstični TS |Savl74|.
DOKAZ: Relacija BPP C PP je očitna iz definicije. PP C PSPACE je posledica izreka o deterministični simulaciji verjetnostnega TS, ki ga tu nismo navedli. Dokaz bi šel podobno kot dokaz izreka 8.
Pokažimo še LVP CBPP. Naj bo L jezik, ki ga raipoznava VTS M i verjetnostjo napake O in povprečnim časom omejenim s polinomom p(n). Bodi c > 2 poljubna konstanta. Z M' označimo VTS, ki simulira delovanje VTS M do največ ep(n) korakov. Ce se M do tedaj ne bi ustavil, M' odgovori karkoli. Ker hi naredi več kot cp(n) korakov z verjetnostjo manj kot l/c, je verjetnost napake polinomsko omejenega stroja hi' največ l/c < 1/2.
Q.E.D.
28.IZREK: P C LVP C NP C PP
DOKAZ: Ker vsak polinomsko omejeni TS računa z verjetnostjo napak t O, je očitno PC LVP.
Bodi L eLVP in hi VTS, ki razpoznava L t verjetnostjo napakt O in polinomsko omejenim povprečnim časom. Ce na M gledamo kot na nedeterministični TS vidimo, da hi razpozna L v polinomskem času, saj mora biti za vsak vhod vsaj en izračun s polinomsko omejenim številom korakov. Torej L 6 NP in LVP C NP.
Pokažimo Se NP C PP. Brez škode za splošnost lahko privzamemo, da L razpoznava polinomsko omejen NTS, ki ima v vsakem stanju največ dva mogoča koraka. Če na hi gledamo kot na verjetnostni stroj, potem je L množica nizov, za katere obstaja sprejemajoč izračun. Torej i£i« Pr( M(z) sprejme} > 0. Za dokaz, da je £ v razredu PP konstruiramo stroj hi' takole: M' najprej vrte kovanec; če je rezultat grb, potem sprejme vhod, sicer pa simulira delovanje stroja M, tako da vsakič, ko ima na voljo dve nadaljevanji, izbere eno ali drugo z enako verjetnostjo (J).
Vendar verjetnostni stroj hi' Se ni povsem dober. Ce z g L je mogoče, da velja Pr{M'(z) sprejme} = 1/2. Torej je mogoče, da M' ne izračuna karakteristične funkcije L. Definiramo VTS M", za katerega bo veljalo Pr{M"(z) sprejme} < 1/2 za vse z-e, ki niso v L.
Bodi p(n) polinom, ki omejuje Število korakov izvajanja stroja hi. Vsak z € L dolžine n je sprejet z verjetnostjo vsaj 2~'<*>, saj gotovo obstaja vsaj en sprejemajoč Izračun in Je verjetnost vsakegaod Izračunov doltine n vsaj 2-»<*>. Verjetnostni TS M" deluje takole: Najprej hi" vrte p(n) + l kovanec in sprejme vhod brez nadaljevanja z verjetnostjo	Potem M" simulira delovanje
M in sprejme vhod, če ga sprejme M. hi" torej zavrne vsak z ( Z, z verjetnostjo vsaj ^ +	in sprejme vsak z 6 i. z verjetnostjo vsaj ^ +	Torej
VTS hi" razpoznavah v polinomskem času, zato NPCPP.
Q.E.D.
29.DEFINICIJA: VPP (ali RP) je razred jezikov, ki jih razpoznajo polinomsko omejeni VTS, ki imajo za vhode, ki niso v jeziku, verjetnost nap&kr 0.
Ali, drugače zapisano:
L € RP a L razpoznava polinomsko omejeni VTS hi in Pr(M(z) sprejme} = O a Vz t L.
Opomba: Tu bi dobili isti razred, če bi za z € L zahtevali Pr(W(z)«prejme} > q za katerokoli konstanto O < q < 1. Po n ponovitvah algoritma je namreč verjetnost napake enaka 1 - (J)(l -
30.IZREK:
1.)	RP C NP n BPP
2.)	LVP = RP n co-RP
DOKAZ: 1.) Inkluziji RP C BPP in RP C NP sta očitni.
2.) Pokazali bomo LVP C RP, LVP C co - RP in RP n co - RP C LVP.
Najprej pokažimo LVP C RP. Ce je i € LVP, lahko L razpoznamo TS hi, katerega pričakovani čas izvajanja je omejen z nekim polinomom, imenujmo ga q, rezultati pa so popolnoma zanesljivi. Konstrulrajmo TS M' takole: • pri vhodu z simulira delovanje TS hi največ i(|x|) korakov. Ce bi se hi ustavil, preden se ustavi hi' (to se zgodi z verjetnostjo vsaj 1/2), potem hi' odgovori isto kot M. Sicer M' odgovori NE. Vidimo, da so pritrdilni odgovori hi' povsem zanesljivi, negativni odgovori pa so pravilni z verjetnostjo 1/2. Torej je £ 6 RP in LVP C RP.
65
Podoben argument pokaže LVP C co - RP.
Ostala nam je še inkluzija RP n co - RP C LVP. Bodi L € RP n co - RP. Potem obstajata VTS Mi in A/j, za katera velja;
-	čas izvajanja obeh VTS je omejen s polinomom
-	pozitivni odgovori Mi in negativni odgovori Mi »o povsem zanesljivi
-	negativni odgovori Mi in pozitivni odgovori Mi so pravilni z verjetnostjo, ki je vetja od neke konstante, na primer 1/2.
Pokažimo, kako lahko konstruiramo TS z verjetnostjo napake 0 in s polinomskim povprečnim časom izvajanjv Bodi z poljuben. Simulirajmo delovanje Mi in delovanje Mi, kar lahko naredimo v polinomskem času. Ce je vs^j en odgovor zanesljiv, končamo. Zanimiv je primer, ko oba algoritma dasta odgovor, ki nI povsem zanesljiv, (verjetnost tega dogodka je manjSa od 1/4). V tem primeru poskus ponovimo, dokler se ne zgodi prvi primer. Pričakovano Število ponovitev poskusa je omejeno (J^J^j (1/4*)}, zato je povprečni potrebni čas omejen s polinomom. Q.E.D.
Za konec navedimo ie nekaj primerov. Začnimo s problemom določitve, ali je neko Število praitevilo.
Problem: PraStevila (PRIMES) Vhod: Naravno Število n v binarnem zapisu. Odgovor: Da, če je n praitevilo in ne, če ni.
31.IZREK:
a)	PRIMES 6 co - NP
b)	PRIMES 6 co - RP
DOKAZ: a) trivialno
b) . Naslednji algoritem (Solovay-Strassen) dokazuje, da je problem PRIMES v razredu co-RP. •izberi a € {1,2,...,n - 1} te (a, n) ji 1 potem n ni praitevilo te (a/n) £ a^r1 (mod n) potem n ni praitevilo
sicer n je (z verjetnostjo > 1/2) praitevilo
kjer je (a/n) Legendrov simbol (prim. lGras75|).
Legendrov simbol znamo učinkovito (v polinomskem Času) izračunati z algoritmom, ki je nekoliko podoben Evklidovemu. Temelji na recipročnem zakonu, ki pravi, da je (?/p) = -(p/?), če je p = ? = 3 in (i/p) = (p/?) sicer. Poleg tega za 4 > p, torej q = mp + r, velja (q/p) = (r/p).
Ce je p praitevilo, je kongruenca
(a/p) = a^(mod p)
izpolnjena za vsa Števila a, 1 < a < p -1. Ce pa p ni praitevilo, pa kongruenca velja za največ polovico a-jev [SoSt77|. Q.E.D.
Neodvisno je podoben dokaz naiel Rabin [Rabi76|. Kot drugi primer si poglejmo naslednja problema: Problem: MAJ
Vhod: (KNO) formulastavčnegaračunaF(ii,...,*«) VpraJanJe: Ali F velja za večino (za več kot 2*"1) naborov vrednosti za »i.....
Problem: #SAT
Vhod: (KNO) formula stavčnega računa ..., z«) in naravno Število
i
Vpralanje: Ali obstaja vsaj i različnih naborov vrednosti ca spremenljivke i¡,..., x», ki zadoičajo F.
KNO je kratica za konjuktivno normalno obliko.
Brez dokaza navedimo (glej npr. [GÍ1I77])
32.IZREK: MAJ in fSAT sta PP-polna problema. 7. Reševanje NP-polnlh problemov
Doslej najboljia ocena za čas, potreben za reievanje NP- polnega problema je eksponentna funkcija dolžine vhoda. Pri velikih n je stvar videti brezupna. Po drugi strani so mnogi praktični problemi dokazano NP-polni. Kaj storiti? Poglejmo nekaj sploinih pristopov:
a)	Posebni primeri: Pogosto s« zgodi, da v praksi ne potrebujemo rediti NP-polnega problema v vsej sploSnosti. Podproblemi imajo zaradi dod&tnih omejitev včasih polinomske rešitve.
b)	DinamlCno programiranje in razveji-omeji sta tehniki, ki ju je mogoče uporabiti pri reševanju nekaterih NP-polnih problemov. V obeh primerih s pametno izbiro nadaljevanja precej zmanjiamo potrebno računanje na neperspektivnih reiitvah. Cas obeh metod pa je Se vedno eksponenten. Več o omenjenih metodah najdemo na primer v knjigi [Koza86|.
c)	Z verjetnostno analizo lahko včasih pokažemo, da so resnično 'težki' primeri NP-polnega problema dokaj redki. V takem primeru lahko najdemo algoritem z dobrim pričakovanim časom računanja, čeprav zgornje meje ne moremo omejiti s polinomom. Seveda je potrebno paziti pri izbiri porazdelitve primerov NP-polnega problema. Dokaz, da je izbrana porazdelitev prava, pa utegne biti resen problem [Karp76).
Za primer omenimo metodo simpleksov za reievanje problema linearnega programiranja, ki ima eksponentno časovno zahtevnost. Metoda simpleksov se v praksi dobro obnese, verjetno zaradi izredne redkosti 'težkih' primerkov problema. Dokazano je namreč, daje metoda v povprečju polinomska |Smal83j. Kljub temu, da je problem linearnega programiranja v razredu P |Khac79), pa ne poznamo polinomskega algoritma, ki bi bil v praksi boljši od metode simpleksov.
d)	Aproksimadjski algoritmi lahko včasih dajo zadovoljive reiitve v kratkem času. Seveda nI vseeno, kaj nam pomeni v konkretnem primeru zadovoljiva rešitev. V primeru barvanja točk grafa na primer velja, da bi bil tudi algoritem, ki bi poiskal skoraj optimalno rešitev NP-poln. Carey in Johnson sta namreč pokazala |GaJo76], da velja: ie za kakšni konstanti r < 2 in i velja, da algoritem A poiSče barvanje z j4(C) < r*(G) + d barvami v polinomskem času, potem obstaja algoritem, ki poiSče x(G)-barvanje v polinomskem času.
e)	Hevristični algoritmi dajejo dobre rezultate na kakJni podmnožici problemske domene. Pri determinističnih hevrističnih algoritmih »e običajno zgodi, da imajo Ahilove pete: na nekaterih primerih se obnaiajo zelo slabo. Ce nekatere korake naredimo slučajno, se običajno izognemo Ahilovim petam na račun nekaj večje (pričakovane) časovne zahtevnosti. Omenimo nekaj hevrističnih algoritmov za problem barvanja točk grafa:
-	Comeil-Grahamov hevristični algoritem temelji na algoritmu Zykova (CoGr73,Gode83|.
-	Veliko hevrističnih algoritmov spada v skupino, imenovano postopki zaporednega barvanja |Bata80|. OpiSemo jih z naslednjo algoritemsko shemo:
pobarvaj točite gra/s s 'prazno' barvo
dokler 3 točka, pobarvana s prazno barvo ponavljaj izberi barvo ca točko v
Ce določimo vrstni red barvanja točk in strategijo izbire barve, dobimo algoritem. Ce na primer točke izbiramo po padajočih stopnjah in izbrano
66
toCko vsakič pobarvamo z najnitjo barvo, ki je Se prosta (noben sosed le ni pobarvan s to barvo), dobimo Welsh-Powellov postopek. Za ta postopek je mogoč« pokazati, da porabi največ d + 1 barv, kjer je i največja stopnja točke v grafu. Vendar (kar pa ni presenetljivo) obstaja drulina grafov, na kateri je razmerje med Številom barv, ki Jih porabi Welsh- Powellov postopek In med dejansko potrebnim Številom barv poljubno veliko (WePo67). V |2ero88a| je podana konstrukcija take d rutine grafov.
algoritem	(Welsh-Petford),	ki
ga obravnavamo v |2ero87,2ero88,2ero88a|, temelji na protivolilnem modelu delcev i Interakcijo i:, statistične mehanike (percolation theory). Je primer verjetnostnega hevrističnega algoritma. Gre za iterativno (slučajno) lokalno 'popravljanje' danega barvanja, ki z verjetnostjo 1 v končno mnogo korakih d ose te neko dobro barvanje, če smo na začetku Izbrali vaaj x(G) barv. Ce algoritem po vnaprej določenem Številu korakov nasilno prekinemo, se nam lahko zgodi, da ne dobimo dobrega barvanja, čeprav to obstaja. Vemo, da je pročakovani čas absorbcije na regularnih grafih reda 0(nJ). Poleg tega se algoritem na testlranlh grafih obnaSa zelo dobro. Zato algoritem z vgrajeno nasilno prekinitvijo (s polinomako mejo dovoljenega Števila korakov) apliciramo na 'vse' grafe in upamo, da bodo rezultati Se vedno dobri.
8. Literatura
VhHU76] A.V.Aho, V.E.Hopcroft, J.D.UIIman: The Design and Analysis of
Computer Algorithms, Addison-Wesley 1976 ApHa86| K.Appel, W.Haken: The Four color Proof Suffices, The Mathematical
Intelligencer, Vol. 8, 1986, No. 1, p.10-20 [Bata80| V.Batagelj: Barvanja točk grafov, Seminar za računalniško In numerično
matematiko 201, Ljubljana 1980 [BaPi85| D.Baje, T.Pisanaki: Najnujnejše o grafih, Presekova knjilnica 22, DMFA S RS, Ljubljana 1986
*
[Cook7l| S .A.Cook: The Complexity of Theorem-proving Procedures, Proc. of Zri Annual ACM Symposium on Theory of Computing, Shaker Heights, Ohio, 151-158, (1971)
CoCr73] D.G.Corneit, B.Graham: An algorithm for determining the chromatic
number of a graph, SIAM J. Comp. 2 (1973) 4, 311-318 CvM177| R,Cvetkov«i , M.Milit : Teorija grafovai njene primjene, Naučna knjiga Beograd, 1977
DoWe83| P.Donnelly, D.Welsh: Finite particle systems and infection models, Math.
Proc. Camb. Phil. Soc (1983), 94, 167-182 DuBrtl] R-D.Dutton, R.C.Brigham: A new graph coloring algorithm, The
Computer Journal 24 (1981) 1, 86-86 GaJo76] M.fLGarey, D.S.Johnson: The Complexity of Near-Optimal Graph
Coloring, JACM 23 (1976) 1, 43-49 GaJo79] M-R-Garey, D.S.Johnson: Computers and Intractability, W.H.Freeman
and Co., (San Francisco) 1979 |Gill77] J.Gill: Computational complexity of probabilistic Turing machines, Siam.
J. Comp. 6 (1977) 4, p.675-695 |Gras75] J.Graaselli: Osnove teorije Števil, tbirka Sigma, DZS 1975 Gode83j H.Godec: Algoritmi za barvanje grafov, diplomsko delo, FNT Ljubljana 1983
[HoU179] V.E.Hopcroft, J.D.UIIman: Introduction to automata theory, languages
and computation, Addison-Wesley 1979 [H0UI86] V.E.Hopcroft, J.D.UIIman: Uvod v teorijo avtomatov .jezikov In izračunov,
(prevod B.Vilfan), Fakulteta z» elektrotehniko, Ljubljana 1986 [Karp72] R.M.Karp: Reducibility among combinatorial problems, v Complexity of Computer Computations (ur. Miller, Thatcher), Plenum Press, New York, 8&-103, (1972)
(Karp76| R_M.Karp: The Probabilistic Analysis of some Combinatorial Search Algorithms, v Algorithms and complexity (ur. Traub), 1-20, Academic Press 1976
[Khac79| L.G.Khatchjan: LP in polynomial time, Doklady Akad. Nauk SSSR 244 (1979) p.1093-1096
[Knut8l] D.E.Knuth: Algorithms in modern mathematics and computer science,
Lecture Notes in Comp. Sci. 122, Springer-Verlag, Berlin 1981 |Koza86] J.Kozak: Podatkovne strukture in algoritmi, DMFA SRS, Ljubljana 1986 LLRS85) E.L.Lawler, J.K.Lenstra, A.H.G.Rlnnooy Kan, D.B.Shmoys: The
Traveling Salesman Problem, Wiley 1985 |Melh84| K.Melhom: Graph Algorithms and NP-Completeness, Springer-Verlag, 1984
|PeP182] M.Petkoviek, T.Pisanski: Izbrana poglavja iz računalništva, I. del, DMFA
SRS, Ljubljana 1982 |Pisa83] T.Pisanski: Izračunljivost in reSljivost, DMFA SRS, Ljubljana 1983 |Rabi76| M.O.Rabin: Probabilistic Algorithms, v Algorithms and Complexity (ur.
Traub), 21-39, Academic Press 1976 *[Savi74| W.J.Savitch: Relationship between nondeterministic and deterministic tape complexities, Journal for Computer and System Sciences (1974), p.177-192
'[Smal83] Smale: On the average number of steps of the simplex method of linear
programming, Math. Prog. 27 (1983) p.241-262 |SoSt77| R.Solovay, V.Strassen: A Fast Monte-Cario Test for Primality, SIAM J.
Comp., Vol. 6, No. 1, March 1977 |Sch»86] U.Schining: Complexity and Structure, Lecture Notes in Comp. Sci. 211,
Springer-Verlag 1986 (Tro«83) V.N.Trostnikov: Sto su konstruktivni procesi u matematici, Modema
matematika, Skolska knjiga Zagreb 1983 WePe83| D.J.A.Welsh, D.M.Petford: A Randomised Attack to an NP-Complete
Problem, Univ. of Oxford (preprint), 1983 WePo67] D.J.A.Welsh, M.B.Powell: An upper bound for the chromatic number of a graph and its application to timetabling problems, The Computer Journal 10 (1967), 86-86
VoWi78] D.R_Woodall, R.J.Wilson: The Appel-Haken Froof of the Four-Colour Theorem, v Selected Topics in Graph Theory I, (ur. L.W.Beineke, R.J.Wilson), Academic Press 1978 [2ero87] J.2erovnik: Poskusi s slučajnim hevrističnim algoritmom, Zbornik XI.
simpozija iz informatike Jahorina 1987, 294-(l-10) |2ero88] J.2erovnik: Randomised Heurística] Algorithm for Graph Colouring, Proceedings of Eighth Yugoslav Seminar on Graph Theory, Novi Sad 1987, (sprejeto)
2ero88a| J.Zerovnik: Verjetnostni algoritem za barvanje grafa, magistersko delo, FNT Ljubljana 1988
Z * smo označili posredne reference.