Klasa složenosti

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

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

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. 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. O se čita kao "redosled...". 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.

Pitanje resursa može biti ili vreme, u suštii broj primitivnih operacija na apstraktne mašine, ili (za skladištenje) prostor. 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.

Najjednostavnije klase složenosti su definisane sledećim faktorima:

• Tip računarskih problema: Najčešće korišćeni problemi su problemi odlučivanja. 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...
• 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.
• 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.

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

Granično vreme izračunavanja neke konkretne fukncije f(n) čsto daje složenost klase koja zavisi od izabranog modela mašine. 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. 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". 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.

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

Važne klase složenosti

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

Klasa složenosti	Model računanja	Ograničenje resursa
DTIME (f(n))	Deterministička Tjuringova mašina	Vreme f(n)
P	Deterministička Tjuringova mašina	Polinomijalno vreme
EXPTIME	Deterministička Tjuringova mašina	Vreme 2polinomijalno(n)
NTIME(f(n))	Nedeterministička Tjuringova mašina	Vreme f(n)
NP	Nedeterministička Tjuringova mašina	Polinomijalno vreme
NEXPTIME	Nedeterministička Tjuringova mašina	Vreme 2polinomijalno(n)
DSPACE(f(n))	Deterministička Tjuringova mašina	Prostor f(n)
L	Deterministička Tjuringova mašina	Prostor O(logn)
PSPACE	Deterministička Tjuringova mašina	Polinomijalni prostor (n)
EXPSPACE	Deterministička Tjuringova mašina	Prostor 2polinomijalno(n)
NSPACE(f(n))	Nedeterministička Tjuringova mašina	Prostor f(n)
NL	Nedeterministička Tjuringova mašina	Prostor O(logn)
NPSPACE	Nedeterministička Tjuringova mašina	Polinomijalni prostor (n)
NEXPSPACE	Nedeterministička Tjuringova mašina	Prostor 2polinomijalno(n)

Ispostavilo se da PSPACE = NPSPACE i EXPSPACE = NEXPSPACE .

Druge važne klase složenosti uključuju BPP, ZPP i RP, koje su definisane koristeći probabilističke Tjurinove mašine. 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). Klase kao IP i AM su definisane korišćenjem interaktivnih dokaza sistema. ALL je klasa za sve probleme odlučivanja.

Redukcija

Mnoge klase složenosti su definisane korišćenjem pojma redukcije. Redukcija je transformacija jednog problema u drugi problem. Ona obuhvata neformalan pojam problema koji je jednako težak kao i drugi problemi. 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.

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

Ova motivacija koncepta problema je teža za klase složenosti. 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. Za klase složenoti veće od P, polinomijalno vreme reduckcije se najčešće koristi. Konkretno, niz problema koji su teški za NP je niz NP - teških problema.

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). 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, Π₁, poznato kao NP-kompletnih problema, Π₂, ukazuje da nema poznatog rešenja polinomijalnog vremena za Π₁. To je zato što rešenje polinomijalnog vremena za Π₁ dobija rešenje polinomijalnog vremena za Π₂. 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.

Zatvorenost osobina klase

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

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. Ovo je, međutim ređe urađeno.

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

Odnosi između klasa složenosti

Sledeća tablica pokazuje neke klase problema (ili jezika, ili grmatika) koji se razmatraju u teoriji složenosti. Ako je klasa X pravi podskup od Y, tada je X dole prikazan ispod Y, pri čemu ih povezuje tamna linija. Ako je X podskup, ali se ne zna jesu li skupovi jednaki, tada je linija svetlija i tačkasta. 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.

		Problem odlučivanja
Tip 0 (Rekurzivno prebrojiv)				Neodlučiv
Odlučiv
EXPSPACE
NEXPTIME
EXPTIME
PSPACE
Tip 1 (Konteksno senzitivan)
		co-NP	BQP		NP
			BPP
		P
	NC
Tip 2 (Konteksno nezavisan)
Tip 3 (Regularan)

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. Konkretno, iako se DTIME(n) nalazi u DTIME(n²), bilo bi poželjno znti da li je uključivanje strogo. Za zahev za vreme i prostor, odgovor na takva pitanja daje Teorema o vremenu prostoru respektivno. Oni se zovu hijerarhijska teorema jer izazivaju odgovarajuću hijerarhiju o klasama definisane ograničavajućim odgovarajućim resursima. Tako postoje parovi klasa složenosti koji su ispravno uključeni jedna u drugu. 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.

Tačnije Teorema vreme hijerarhije navodi da:

$\operatorname {DTIME} {\big (}f(n){\big )}\subsetneq \operatorname {DTIME} {\big (}f(n)\cdot \log ^{2}(f(n)){\big )}$.

Teorema prostor hijerarhije navodi da:

$\operatorname {DSPACE} {\big (}f(n){\big )}\subsetneq \operatorname {DSPACE} {\big (}f(n)\cdot \log(f(n)){\big )}$.

Teorema vreme i prosto hijerarhije predsravljaju osnovu za većinu rezultta klasa složenosti razdvajanja. 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.

Literatura

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