Računska teorija složenosti
From Wikipedia, the free encyclopedia
Kao grana teorije računanja u računarstvu, računska teorija složenosti opisuje skalabilnost algoritama, te inherentnu teškoću u pružanju skalabilnih algoritama za specifične računske probleme. To jest, teorija odgovara na pitanje, "Kako se veličina ulaza algoritma povećava, kako se mijenjaju vrijeme izvršavanja i memorijski zahtjevi algoritma?". Teorija određuje praktične granice na ono što računala mogu obaviti.
Implikacije teorije su važne vladi i industriji. Brzina i memorijski kapacitet računala uvijek rastu, baš kao i veličine skupova podatka koje treba analizirati. Ako algoritam ne uspije skalirati, tada će velika poboljšanja u računarskoj tehnologiji rezultirati tek u marginalnim povećanjima u praktičnim skupovima podataka.
Algoritmi i problemi su kategorizirani u klase složenosti. Najvažnije otvoreno pitanje teorije složenosti jest pitanje istovjetnosti klase P i klase NP, odnosno je li prva podskup druge kao što se općenito smatra. Daleko od toga da se radi o ezoteričnoj vježbi - ubrzo nakon što je pitanje prvi put postavljeno, shvatilo se da su mnogi važni industrijski problemi u polju operacijskih istraživanja potklasa od NP zvana NP-potpuni problemi. NP-potpuni problemi imaju svojstvo da im se rješenja mogu brzo provjeriti, s tim da trenutne metode pronalaženja problema nisu skalabilne. Ako je klasa NP veća od P, tada ne postoji nijedno skalabilno rješenje za ove probleme. Je li to uistinu tako, je jedno od važnih otvorenih pitanja u računskoj teoriji složenosti.