Uticaj matematike na nastanak i temelje računarstva (3. deo)

Među prve rezultate spadaju i rezultati o nemogućnosti rešavanja nekih problema algoritmom. Jedan od takvih rezultata je i problem zaustavljanja koji se sastoji u tome da za dati program na ulazu, koji sam ne zahteva nikakav ulaz, odredimo da li bi se taj program jednom pušten u rad završio u konačnom broju koraka.

Drugi srodan rezultat je da nije moguće napraviti programski jezik koji bi obuhvatio sve algoritme i čiji bi se svi programi zaustavljali u konačnom broju koraka. Da bi neki programski jezik obuhvatio sve algoritme (zaustavljive postupke), on mora da dopušta i konstrukcije kao što su beskonačne petlje, tj. konstrukcije koje mogu da rade, a da se nikada ne zaustave. Najveći broj programskih jezika je baš takav, a ima i sistema kod kojih se žrtvuje obuhvatanje svih algoritama zarad univerzalne zaustavljivosti. Primer je pomoćnik u dokazivanju teorema Agda.

Osim dokazivanja da neki problemi nisu algoritamski rešivi, izučava se i algoritamska složenost problema koji se mogu algoritamski rešiti. Složenost određenog algoritma za rešavanje nekog problema su resursi (vremenski ili memorijski ili i jedni i drugi) za njegovo izvršavanje, dok je složenost problema zapravo složenost najefikasnijeg mogućeg algoritma za njegovo rešavanje. Ponekad možemo znati da za neki zadatak imamo optimalan algoritam, ali to najčešće nije slučaj jer je to jako teško dokazati.

Ponekad je dobro što su neki problemi algoritamski jako teški jer ne želimo da budu rešeni. Takvi su problemi razbijanja kriptografskih primitiva čije bi rešavanje dovelo do zloupotreba. Bilo bi jako dobro da imamo kriptografske primitive za koje imamo dokaze da se ne mogu razbiti bez određenih izračunatih resursa koji prevazilaze snagu bilo kakvog hardvera koji se može proizvesti. Međutim, to nije slučaj, a isključivi razlog je što još uvek nije dostignut potreban stepen razvoja matematike. Za sada se kriptografska bezbednost proverava empirijski, tako što se algoritmi objavljuju u naučnim časopisima, pa ako se za određen broj godina niko nije javio sa postupkom razbijanja, onda se algoritam smatra bezbednim. Svakako bi bolje bilo imati dokaz bezbednosti.

Kriptografske primitive treba svakako da budu efikasne za upotrebu na predviđen način, a što teže za razbijanje. Obično se kao zahtev za efikasnom upotrebom uzima da broj koraka bude ograničen polinomom po složenosti ulaza (ovde je to veličina ključa). Za takve probleme se kaže da pripadaju klasi složenosti P. Kao zahtev za teško rešavanje se obično uzima da broj koraka raste eksponencijalno u odnosu na složenost ulaza.

Sve primitive se mogu razbiti u polinomijalnom vremenu na mašinama sa neograničenim paralelizmom (npr. beskonačnim brojem procesora koji mogu paralelno da rade). Ako tražimo privatni ključ od 100 bitova kada je dat javni ključ, mi zapravo treba da proverimo sve moguće nizove od 100 bitova, koji od njih čini privatni ključ koji se slaže sa datim javnim. Prvo možemo problem podeliti na dva slučaja – one kod kojih je prvi bit jednak 0 i one kod kojih je prvi bit jednak 1. Te slučajeve mogu da obrađuju dva procesora paralelno. Zatim, svaki od ta dva slučaja podelimo na dva podslučaja – kada je drugi bit jednak 0 i kada je drugi bit jednak 1. Te podslučajeve mogu paralelno da obrađuju četiri procesora. Tako ćemo u sto koraka cepanja svakog od podslučajeva na dva podslučaja u sto koraka uposliti procesore od kojih svaki obrađuje jedan niz od 100 bitova i svi rade paralelno. To omogućava da se na takvim mašinama taj problem reši efikasno. Slična ideja se može primeniti i na razbijanje simetričnih ključeva i kriptografskih heš (eng. hash) funkcija.

Za takve probleme se kaže da pripadaju klasi NP, koja iz navedenih razloga čini teorijski maksimum kriptografske bezbednosti.

Za klase P i NP se još uvek ne zna da li su iste ili različite. Za rešenje tog problema je čak ponuđena nagrada od milion američkih dolara i on svakako predstavlja centralni nerešeni problem teorijskog računarstva. Ako su te klase jednake, s obzirom na to da problemi razbijanja uvek pripadaju klasi NP, oni u tom slučaju pripadaju i klasi P, što znači da je efikasno razbijanje moguće, pa bi primena kriptografije bila znatno ograničena i otežana. U suprotnom ostaje mogućnost da postoji problem koji je primenljiv na kriptografiju i ima potrebne osobine. Stoga je u svakom slučaju neophodno rešiti taj problem da bi se stiglo do primena u kriptografiji.

Mada je mašine sa neograničenim paralelizmom nemoguće napraviti, one nužno učestvuju u formulacijama stavova relevantnih istraživanja, koja se sprovode jer je priroda problema takva. Drugačije nije moguće doći do rezultata jer je preduslov za neosporan dokaz nekog stava da stav po svojoj formulaciji bude tačan.

Čak i kada se to uspe, ostaje još jedan problem. Fizičari su otkrili drugačiji pristup izračunavanju tzv. kvantnim računarima, koji mada mogu da rešavaju potpuno iste probleme kao klasični (tj. ne dovode u pitanje Čerč-Tjuringovu tezu), neke probleme mogu da rešavaju i efikasnije, gde spadaju i problemi razbijanja nekih (ne svih) kriptografskih algoritama. Stoga treba dokazati otpornost i na napade kvantnim računarima (tzv. problem postkvantne kriptografije), što je još teži zadatak.

Za kraj, pomenimo jedan pravac istraživanja koji objedinjuje formalizaciju matematike i formalizaciju pojma algoritma.

Programi se obično testiraju na konačnom broju primera. Mada se primeri pažljivo biraju tako da verovatnoća neispoljavanja greške ako postoji bude što manja, obično nešto promakne. Drugi put je formalna provera softvera, gde se željene osobine nekog programskog koda dokazuju kao teoreme. Međutim, pošto su ljudi podložni greškama, dokaze treba da proveri mašina.

U tom pogledu, najpre imamo proveravače dokaza kojima mora celokupan dokaz biti dat na ulazu. S obzirom na to da je ljudima naporno da unose baš svaki korak dokaza, drugi pristup su dokazivači teorema koji automatski dokazuju zadatu teoremu. Međutim, pošto se ispostavilo da je taj cilj za većinu matematičkih teorija čak nedostižan, zlatna sredina su pomoćnici u dokazivanju koji takođe zahtevaju dokaz na ulazu, ali ne svaki korak, jer imaju „ograničenu pamet”, tako da čovek ne mora da unosi baš svaki korak, već samo ono za šta mašina kaže da joj je ostalo „nejasno”.

Vodeći takvi programi su Isabelle, Coq i Agda, pri čemu su svi oni akademski projekti dostupni kao slobodan softver otvorenog koda. To je u ovom slučaju čak neophodno, jer je provera ispravnosti programa koji proverava dokaz, sastavni deo naučne provere dokaza koje ti programi proveravaju. Stoga je taj model uobičajen za akademske projekte, jer u suprotnom ne bi bilo moguće naučno pozivanje na rezultate koji se njima dobijaju.

Loša vest je da takav pristup, mada eliminiše greške u izvornom kodu u celini (a pristup je primenljiv i na druge softverske komponente, kao i na hardver), zahteva mnogo kvalifikovaniju radnu snagu od klasične i samim tim je daleko skuplji, pa se za sada primenjuje samo za namene visokog rizika, gde može doći do gubitka ljudskih života, narušavanja ljudskog zdravlja ili velike materijalne štete.

Ipak, verujemo da taj pristup ima širu budućnost (mada ne tako skoru). Svaki programski jezik omogućava izradu softvera do neke složenosti, kada ljudi počinju da prave više novih grešaka, nego što ispravljaju stare. Sa ovim pristupom nema granica u složenosti, tako da postepeno mogu da budu pravljene složene komponente koje će da koriste i ostali koji razvijaju softver.

Prethodni deo