Klasa složenosti
<s>Klasa složenosti u teoriji računarske složenosti je skup problema povezanih resursima zasnovanim na složenosti.</s><s>Tipična složenost klasa ima definiciju oblika:</s>

<s>skup problema koji se mogu rešiti apstraktnom mašinom M korišćenjem O(f(n)) resursa R, gde je n veličina ulaza.</s>

<s>Složene klase su zabrinute sa stopom rasta zahteva za resurse kao i povećavanje ulaza n. To je apstraktno merenje, i ne daje vreme ili prostor u sekundi ili bajtu, što zahteva poznavanje implementacije specifičnosti.</s><s>Funkcija unutar O(...) izraza može biti konstanta, za algoritme koji su pod uticajem veličine n, ili izraza koji sadrži logaritam, izraz uključuje n, odnosno polinomni izraz, i mnoge druge.</s><s>O se čita kao "redosled...".</s><s>Za potrebe izračunavanja teorije složenosti, neke od detalja funkcije se mogu zanemariti, na primer mnogo mogućih polinoma može biti grupisano kao klasa.</s>

<s>Pitanje resursa može biti ili vreme, u suštii broj primitivnih operacija na apstraktne mašine, ili (za skladištenje) prostor.</s><s>Na primer, klasa NP je skup svih problema odlučivanja koji mogu biti rešeni nedeterminističkom Tjuringovom mašinom u polinomijalnom vremenu dok je klasa PSPACE skup svih problema odluke koji mogu biti rešeni determinističkom Tjuringovom mašinom u polinomijalnom prostoru.</s>

<s>Najjednostavnije klase složenosti su definisane sledećim faktorima:
Tip računarskih problema: Najčešće korišćeni problemi su problemi odlučivanja.</s><s>Međutim, klase složenosti se mogu definisati na osnovu funkcijskih problema (primer je FP), računarskih problema (npr.#P), optimizacionih problema, obećavajućih problema itd...</s><s>Model računanja: Najčešći model računanja je deterministička Tjuringova mašina, ali mnoge klase složenosti su zasnovane na nedeterminističkim Tjuringovim mašinama, logički sklop, kvantna Tjuringova mašina, monoton sklop, itd.</s><s>Resurs(ili resursi) koji se graniče i granice: Ove dve osobine se obično navode zajedno, kao što su "polinomijalno vreme", "logaritamski prostor", "konstantna dubina", itd.</s>

<s>Mnoge klase složenosti se mogu okarakterisati kao matematička logika koja želi da ih izrazi;</s>

<s>Granično vreme izračunavanja neke konkretne fukncije f(n) čsto daje složenost klase koja zavisi od izabranog modela mašine.</s><s>Na primer, jezik {xx | x je bilo koji binarni niѕ} može da e reši u linearnom remenu na multi-traci Tjuringove mašine, ali nužno zahteva kvadratno vreme u modelu jedne-trake Tjuringove mašine.</s><s>Ako dozvolimo polinomijalnu varijaciju u tekućem vremenu, Cobham-Edmonds teza glasi da je "vremenska složenost bilo koja dva razumna i opšta modela obračuna su polinomijalno vezana".</s><s>Ovo predstavlja osnovu za složenost klase P, koja je niz datih problema odluke rešena determinističkom Tjuringovom mašinom u polinomijalnom vremenu odgovarajućeg skupa funkcijiskih problema je FP.</s>

<s>Blumove aksiome se mogu koristiti za definisanje klasa složenosti bez pozivanja na neki konkretni računski model.</s>

<s>Važne klase složenosti 
Mnoge važne klase složenosti mogu biti definisane pomoću granica vremena ili prostora koje koristi algoritam.</s><s>Neke važne klase složenosti donošenja problema definisane su na sledeći način:</s>

<s>Ispostavilo se da PSPACE = NPSPACE i EXPSPACE = NEXPSPACE .</s>

<s>Druge važne klase složenosti uključuju BPP, ZPP i RP, koje su definisane koristeći probabilističke Tjurinove mašine.</s><s>AC i NC, koje su definisane koristeći logički sklop i BQP i QMA, koje su definisane pomoću kvntne Tjuringove mašine. #P je vazžna klasa složenosti broja problema (nisu problemi odlučivanja).</s><s>Klase kao IP i AM su definisane korišćenjem interaktivnih dokaza sistema.</s><s>ALL je klasa za sve probleme odlučivanja.</s>

<s>Redukcija 
Mnoge klase složenosti su definisane korišćenjem pojma redukcije.</s><s>Redukcija je transformacija jednog problema u drugi problem.</s><s>Ona obuhvata neformalan pojam problema koji je jednako težak kao i drugi problemi.</s><s>Na primer, ako se problem X može rešiti korišćenjem algoritma Y, X nije mnogo teži od Y, i mi kažemo da je X redukcija Y. Postoji mnogo različitih vrsta redukcije, na osnovu metoda redukcije, kao što je Cook redukcija, Karp redukcija i Levin redukcija, i granice složenosti redukcije tako da je smaljeno polinomijalno vreme ili smanjen logaritamski prostor.</s>

<s>Najčešća upotreba redukcije polinomijalno vreme redukcije.</s><s>To znači da je za poces redukcije potrebno polinoijalno vreme.</s><s>Na primer, problem kvadriranja celog broja može da se redukuje na problem množenja dva cela broja.</s><s>To znači da algoritam za množenje dva cela broja može da se koristi za kvadratni ceo broj.</s><s>Zaista, to može da se uradi tako što je isti ulaz za oba ulaza množenja algoritama.</s><s>Tako vidimo da kvadriranje nije teže od množenja, jer kvadriranje može da se svede na množenje.</s>

<s>Ova motivacija koncepta problema je teža za klase složenosti.</s><s>Problem X je teži od klase problema C ako svaki problem u C može biti redukcija od X. Problem u C je teži nego u X, jer nam algoritam za X omogućava da rešimo svaki problem u C. Naravno, pojam teški problemi zavisi od redukcije koja se koristi.</s><s>Za klase složenoti veće od P, polinomijalno vreme reduckcije se najčešće koristi.</s><s>Konkretno, niz problema koji su teški za NP je niz NP - teških problema.</s>

<s>Ako je problem X i C i teško C, onda je X potpuno za C. To znači da je X najteži problem u C. (Od mnogo problema koji su podjednako teški, moglo bi se reći da je X jedan od najtežih problema u C).</s><s>Tako klasa NP-kompletnih problema sadrži najteže probleme u NP, u smislu da oni najverovatnije ne bi bili u P. Pošto problem P = NP nije rešen, postoji mogućnost da se redukuje drugi problem, Π1, poznato kao NP-kompletnih problema, Π2, ukazuje da nema poznatog rešenja polinomijalnog vremena za Π1.</s><s>To je zato što rešenje polinomijalnog vremena za Π1 dobija rešenje polinomijalnog vremena za Π2.</s><s>Slično tome, jer svi NP problemi se mogu svesti na redukciju niza, za pronalaženje NP-kompletnih problema koji se mogu rešiti u polinomijalnom vremenu važi P = NP.</s>

<s>Zatvorenost osobina klase 
Klase složenosti imaju različite osobine zatvorenosti.</s><s>Na primer, odluka klase može biti zatvorena pod negacijom, disjunkcijom, konjukcijom ili čak u svim logičkim operacijama.</s><s>Osim toga, one takože mogu biti zatvorene pod raznim kvantifikacijama šeme.</s><s>P, na primer, je ѕatvoren prema svim logičkim operacijama, a kvantifikacija preko polinomijalne veličine domena.</s><s>Međutim, to najverovatnije nije zatvorenost za kvantifikaciju reko eksponencijalne velčine domena.</s>

<s>Svaka klasa X koja nije zatvorena pod negacijom ima dodatak klase co-Y, koja se sastoji od komplemenata koji su sadržani u X. Slično se može definisati i logičko zatvorenje klase, itd.</s><s>Ovo je, međutim ređe urađeno.</s>

<s>Jedan od mogućih puteva za razdvajanje dve klase složenosti je da se pronađe osobina zatvorenja jednog, a ne drugog.</s>

<s>Odnosi između klasa složenosti 
Sledeća tablica pokazuje neke klase problema (ili jezika, ili grmatika) koji se razmatraju u teoriji složenosti.</s><s>Ako je klasa X pravi podskup od Y, tada je X dole prikazan ispod Y, pri čemu ih povezuje tamna linija.</s><s>Ako je X podskup, ali se ne zna jesu li skupovi jednaki, tada je linija svetlija i tačkasta.</s><s>Tehnički, podela u odlučive i neodlučive probleme više spada u teoriju izračunljivosti, ali i pomaže u pružanju perspektive nad klasama složenosti.</s>

<s>Hijerarhija teorema 
Za klase složenosti definisane na ovaj način, poželjno je dokazati da opuštanje uslova za (recimo) računanje vremena zaista definiše veći skup problema.</s><s>Konkretno, iako se DTIME(n) nalazi u DTIME(n2), bilo bi poželjno znti da li je uključivanje strogo.</s><s>Za zahev za vreme i prostor, odgovor na takva pitanja daje Teorema o vremenu prostoru respektivno.</s><s>Oni se zovu hijerarhijska teorema jer izazivaju odgovarajuću hijerarhiju o klasama definisane ograničavajućim odgovarajućim resursima.</s><s>Tako postoje parovi klasa složenosti koji su ispravno uključeni jedna u drugu.</s><s>Pošto je zaključio takve prave postavljene dodatke, možemo da nastavimo o kvantitivnim izjavama o tome kako je potrebno mnogo više dodatnog vremena ili prostora u cilju povećanja broja problema koji se mogu rešiti.</s>

<s>Tačnije Teorema vreme hijerarhije navodi da:
.</s>

<s>Teorema prostor hijerarhije navodi da:
.</s>

<s>Teorema vreme i prosto hijerarhije predsravljaju osnovu za većinu rezultta klasa složenosti razdvajanja.</s><s>Na primer, Teorema vreme hijerahije nam govori da li je P strogo sadržan u EXPTIME, a Teorema prostor hijerarhije nam govori da je L strogo sadržan u PSPACE.</s>

<s>Literatura 
 The Complexity Zoo : Ogromni popis klasa složenosti, kao referenca za eksperte.</s><s>Dijagram  Neila Immermana koji prikazuje hijerarhiju klasa složenosti i kako se one nadopunjuju.</s><s>Michael Garey i David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness.</s><s>New York: W. H. Freeman & Co., 1979.</s><s>Standardna referenca za NP-potpune probleme - važne kategorije problema čija rješenja naizgled zahtijevaju nepraktično mnogo vremena za računanje.</s>

<s>Teorija kompleksnosti</s>

