Osnove teorije računske kompleksnosti EITC/IS/CCTF

Ker se količina sredstev, potrebnih za zagon algoritma, razlikuje glede na velikost vhoda, je kompleksnost običajno izražena kot funkcija f(n), kjer je n velikost vhoda in f(n) bodisi najslabši primer zapletenosti ( največja količina potrebnih virov za vse vložke velikosti n) ali povprečna kompleksnost primera (povprečje količine virov za vse vložke velikosti n). Število zahtevanih elementarnih operacij na vhodu velikosti n je običajno navedeno kot časovna kompleksnost, pri čemer se domneva, da osnovne operacije trajajo konstantno količino časa na določenem računalniku in se spreminjajo samo za konstanten faktor, ko se izvajajo na drugem računalniku. Količina pomnilnika, ki jo zahteva algoritem na vhodu velikosti n, je znana kot prostorska kompleksnost.

Čas je najpogosteje obravnavan vir. Kadar se izraz »zapletenost« uporablja brez kvalifikatorja, se običajno nanaša na kompleksnost časa.

Tradicionalne časovne enote (sekunde, minute itd.) se v teoriji kompleksnosti ne uporabljajo, saj so preveč odvisne od izbranega računalnika in napredka tehnologije. Na primer, današnji računalnik lahko izvede algoritem bistveno hitreje kot računalnik iz šestdesetih let prejšnjega stoletja, vendar je to posledica tehnoloških prebojev v računalniški strojni opremi in ne inherentne kakovosti algoritma. Cilj teorije kompleksnosti je kvantificirati inherentne časovne potrebe algoritmov ali temeljne časovne omejitve, ki bi jih algoritem naložil vsakemu računalniku. To dosežemo s štetjem, koliko osnovnih operacij se izvede med izračunom. Ti postopki se običajno imenujejo koraki, ker velja, da na določenem stroju trajajo konstanten čas (tj. nanje ne vpliva količina vnosa).

Drug pomemben vir je količina računalniškega pomnilnika, ki je potreben za izvajanje algoritmov.

Drug pogosto uporabljen vir je količina aritmetičnih operacij. V tem scenariju se uporablja izraz "aritmetična kompleksnost". Časovna kompleksnost je na splošno produkt aritmetične kompleksnosti s konstantnim faktorjem, če je znana zgornja omejitev velikosti binarne predstavitve števil, ki se pojavijo med izračunom.

Velikost celih števil, uporabljenih med izračunom, ni omejena za številne metode in nerealno je domnevati, da aritmetične operacije zahtevajo določen čas. Posledično je lahko časovna zapletenost, znana tudi kot bitna kompleksnost, bistveno višja od aritmetične kompleksnosti. Aritmetična težava pri izračunu determinante celoštevilske matrike nn je na primer O(n^3) za standardne tehnike (Gaussova eliminacija). Ker se lahko velikost koeficientov med izračunom eksponentno poveča, je bitna kompleksnost istih metod eksponentna v n. Če se te tehnike uporabljajo v povezavi z večmodularno aritmetiko, se lahko kompleksnost bitov zmanjša na O(n^4).

Zapletenost bitov se v formalnem smislu nanaša na število operacij na bitih, potrebnih za izvajanje algoritma. V večini paradigem računanja je enaka časovni kompleksnosti do konstantnega faktorja. Število operacij na strojnih besedah, ki jih zahtevajo računalniki, je sorazmerno z bitno kompleksnostjo. Za realistične modele računanja sta tako časovna in bitna kompleksnost enaki.

Vir, ki se pogosto upošteva pri razvrščanju in iskanju, je količina primerjav vnosov. Če so podatki dobro urejeni, je to dober pokazatelj časovne zapletenosti.

Na vseh potencialnih vhodih je štetje števila korakov v algoritmu nemogoče. Ker kompleksnost vhoda narašča z njegovo velikostjo, je običajno predstavljena kot funkcija velikosti vhoda n (v bitih), zato je kompleksnost funkcija n. Za vhode enake velikosti pa se lahko kompleksnost algoritma močno razlikuje. Posledično se rutinsko uporabljajo različne kompleksne funkcije.

Najslabša zapletenost je vsota vse kompleksnosti za vse vhode velikosti n, medtem ko je kompleksnost povprečnega primera vsota vse zapletenosti za vse vhode velikosti n (to je smiselno, saj je število možnih vhodov dane velikosti končno). Kadar se izraz »zapletenost« uporablja, ne da bi bil dodatno opredeljen, se upošteva časovna zapletenost v najslabšem primeru.

Zapletenost najslabšega in povprečnega primera je znano težko pravilno izračunati. Poleg tega imajo te natančne vrednosti malo praktične uporabnosti, ker bi kakršna koli sprememba stroja ali paradigme izračuna nekoliko spremenila kompleksnost. Poleg tega uporaba virov ni pomembna za majhne vrednosti n, zato je enostavnost izvedbe pogosto privlačnejša od nizke kompleksnosti za majhne vrednosti n.

Zaradi teh razlogov je največ pozornosti namenjene obnašanju kompleksnosti pri velikem n, to je njenemu asimptotičnemu obnašanju, ko se n približuje neskončnosti. Posledično se za označevanje kompleksnosti običajno uporablja velika oznaka O.

Računalni modeli

Pri določanju kompleksnosti je pomembna izbira računskega modela, ki je sestavljen iz specifikacije bistvenih operacij, ki se izvajajo v časovni enoti. To se včasih imenuje Turingov stroj z več trakovi, kadar računska paradigma ni posebej opisana.

Deterministični model računanja je tisti, v katerem so naslednja stanja stroja in operacije, ki jih je treba izvesti, v celoti opredeljena s prejšnjim stanjem. Rekurzivne funkcije, lambda račun in Turingovi stroji so bili prvi deterministični modeli. Stroji z naključnim dostopom (znani tudi kot RAM-stroji) so priljubljena paradigma za simulacijo računalnikov v resničnem svetu.

Kadar računalniški model ni definiran, se običajno domneva, da je Turingov stroj z več trakovi. Na Turingovih strojih z več trakovi je časovna kompleksnost enaka kot pri strojih RAM za večino algoritmov, čeprav je za dosego te enakovrednosti morda potrebna velika pozornost pri tem, kako so podatki shranjeni v pomnilniku.

V nekaterih korakih računanja v nedeterminističnem modelu računalništva, kot so nedeterministični Turingovi stroji, je mogoče narediti različne izbire. V teoriji kompleksnosti se vse izvedljive možnosti obravnavajo hkrati, nedeterministična časovna kompleksnost pa je količina časa, ki je potreben, ko se vedno sprejmejo najboljše izbire. Povedano drugače, izračun poteka hkrati na toliko (identičnih) procesorjih, kolikor je potrebnih, in nedeterministični računski čas je čas, ki ga prvi procesor potrebuje za dokončanje izračuna. Ta vzporednost se lahko uporablja v kvantnem računanju z uporabo superponiranih zapletenih stanj pri izvajanju specializiranih kvantnih algoritmov, kot je na primer Shorova faktorizacija drobnih celih števil.

Tudi če tak računalniški model trenutno ni izvedljiv, ima teoretični pomen, zlasti v zvezi s problemom P = NP, ki sprašuje, ali so razredi kompleksnosti, proizvedeni z uporabo »polinomskega časa« in »nedeterminističnega polinomskega časa« kot najmanjše zgornje meje so enake. Na determinističnem računalniku simulacija NP-algoritma zahteva »eksponentni čas«. Če je mogoče nalogo rešiti v polinomskem času na nedeterminističnem sistemu, spada v težavnostni razred NP. Če je težava v NP in ni lažja kot katera koli druga težava NP, se reče, da je NP-popolna. Problem nahrbtnika, problem potujočega prodajalca in problem Booleove izpolnitve so vsi NP-popolni kombinatorični problemi. Najbolj znan algoritem ima eksponentno kompleksnost za vse te težave. Če bi bilo katero od teh vprašanj mogoče rešiti v polinomskem času na determinističnem stroju, bi lahko vse NP probleme rešili tudi v polinomskem času in bi bilo ugotovljeno P = NP. Od leta 2017 se splošno domneva, da je P NP, kar pomeni, da je najslabše situacije problemov NP v osnovi težko rešiti, tj. traja veliko dlje od katerega koli izvedljivega časovnega obdobja (desetletja) glede na zanimive vhodne dolžine.

Vzporedno in porazdeljeno računalništvo

Vzporedno in porazdeljeno računalništvo vključuje delitev obdelave na več procesorjev, ki vsi delujejo hkrati. Temeljna razlika med različnimi modeli je način pošiljanja podatkov med procesorji. Prenos podatkov med procesorji je pri vzporednem računanju običajno zelo hiter, medtem ko se prenos podatkov med procesorji pri porazdeljenem računanju izvaja po omrežju in je zato bistveno počasnejši.

Izračun na N procesorjih traja vsaj kvocient za N časa, ki ga potrebuje en sam procesor. V resnici, ker nekaterih podopravil ni mogoče vzporediti in bodo nekateri procesorji morda morali čakati na rezultat drugega procesorja, te teoretično idealne omejitve nikoli ne bomo dosegli.

Ključno vprašanje kompleksnosti je torej razviti algoritme, tako da je produkt računalniškega časa s številom procesorjev čim bližje času, ki je potreben za izvedbo enakega računanja na enem samem procesorju.

Kvantno računanje

Kvantni računalnik je računalnik z računalniškim modelom, ki temelji na kvantni mehaniki. Church-Turingova teza velja za kvantne računalnike, kar pomeni, da lahko vsako težavo, ki jo lahko reši kvantni računalnik, reši tudi Turingov stroj. Vendar pa bi nekatere naloge teoretično lahko rešili s kvantnim računalnikom in ne s klasičnim računalnikom z bistveno nižjo časovno kompleksnostjo. Zaenkrat je to strogo teoretično, saj nihče ne ve, kako razviti praktičen kvantni računalnik.

Teorija kvantne kompleksnosti je bila ustvarjena za raziskovanje različnih vrst vprašanj, ki jih lahko rešijo kvantni računalniki. Uporablja se v postkvantni kriptografiji, ki je proces ustvarjanja kriptografskih protokolov, ki so odporni na napade kvantnih računalnikov.

Kompleksnost problema (spodnje meje)

Najmanj zapletenosti algoritmov, ki lahko rešijo problem, vključno z neodkritimi tehnikami, je kompleksnost problema. Posledično je kompleksnost problema enaka kompleksnosti katerega koli algoritma, ki ga rešuje.

Posledično vsaka kompleksnost, podana z velikim zapisom O, predstavlja kompleksnost tako algoritma kot spremljajočega problema.

Po drugi strani pa je pridobivanje netrivialnih spodnjih mej kompleksnosti vprašanja pogosto težko in za to je malo strategij.

Za rešitev večine težav je treba prebrati vse vhodne podatke, kar zahteva čas, sorazmeren z velikostjo podatkov. Posledično imajo takšni problemi vsaj linearno kompleksnost ali, v veliki omega zapisu, kompleksnost Ω(n).

Nekateri problemi, kot so tisti v računalniški algebri in računalniški algebraični geometriji, imajo zelo velike rešitve. Ker mora biti izhod napisan, je kompleksnost omejena z največjo velikostjo izhoda.

Število primerjav, potrebnih za algoritem razvrščanja, ima nelinearno spodnjo mejo Ω(nlogn). Kot rezultat, so najboljši algoritmi za razvrščanje najučinkovitejši, saj je njihova kompleksnost O(nlogn). Dejstvo, da obstaja n! načinov organiziranja n stvari vodi do te spodnje meje. Ker vsaka primerjava deli to zbirko n! naročila na dva dela, mora biti število N primerjav, potrebnih za razlikovanje vseh vrst, 2N > n!, kar pomeni O(nlogn) po Stirlingovi formuli.

Zmanjšanje težave na drugo težavo je običajna strategija za doseganje omejitev zmanjšane kompleksnosti.

Razvoj algoritma

Ocenjevanje kompleksnosti algoritma je pomemben element procesa načrtovanja, saj zagotavlja koristne informacije o zmogljivosti, ki jo lahko pričakujemo.

Pogosto nerazumevanje je, da bo zaradi Moorovega zakona, ki napoveduje eksponentno rast sodobne računalniške moči, ocenjevanje kompleksnosti algoritmov postalo manj pomembno. To ni pravilno, ker povečana moč omogoča obdelavo ogromnih količin podatkov (big data). Na primer, vsak algoritem bi moral dobro delovati v manj kot eni sekundi, ko abecedno razvršča seznam nekaj sto vnosov, kot je bibliografija knjige. Po drugi strani pa bi morali za milijon vnosov (na primer telefonske številke velikega mesta) osnovni algoritmi, ki zahtevajo O(n2) primerjav, izvesti bilijon primerjav, kar bi trajalo tri ure pri hitrosti 10 milijon primerjav na sekundo. Hitro razvrščanje in razvrščanje z združevanjem pa zahtevata le primerjave nlogn (kot zahtevnost povprečnega primera za prvo, kot zapletenost v najslabšem primeru za slednjo). To povzroči približno 30,000,000 primerjav za n = 1,000,000, kar bi trajalo le 3 sekunde pri 10 milijonih primerjav na sekundo.

Posledično lahko ocena kompleksnosti omogoči odpravo številnih neučinkovitih algoritmov pred izvedbo. To se lahko uporablja tudi za natančno nastavitev kompleksnih algoritmov, ne da bi morali testirati vse možne različice. Študija kompleksnosti omogoča osredotočanje prizadevanj za povečanje učinkovitosti implementacije z določitvijo najdražjih korakov kompleksnega algoritma.