EXPTIME

U računarskoj teoriji složenosti, klasa složenosti EXPTIME koja se povremeno naziva EXP ili DEXPTIME, je skup svih problema odlučivanja koji imaju eksponencijalno vreme izvršenja, t.j., koji su rešivi pomoću determinističke Tjuringove mašine u O(2^p(n)) vremenu, gde je p(n) polinomijalna funkcija od n. U terminima DTIME:

${\mbox{EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{ DTIME }}\left(2^{n^{k}}\right).$

Znamo da važi:

P $\subseteq$ NP $\subseteq$ PSPACE $\subseteq$ EXPTIME $\subseteq$ NEXPTIME $\subseteq$ EXPSPACE

a prema teoremama o hijerarhiji vremena i prostora, da je:

P $\subsetneq$ EXPTIME   and   NP $\subsetneq$ NEXPTIME   and   PSPACE $\subsetneq$ EXPSPACE

Tako, barem jedna od prve tri inkluzije i barem jedna od druge tri prikazane inkluzije moraju da budu pravilne, ali nije poznato koje. Većina stručnjaka veruje da su sve inkluzije pravilne. Takođe je poznato da, ako je P = NP, važi i da je EXPTIME = NEXPTIME, klasi problema rešivih u eksponencijalnom vremenu na nedeterminističkoj Tjuringovoj mašini. Tačnije EXPTIME ≠ NEXPTIME, ako i samo ako postoje oskudni jezici (sparse languages) u NP koji nisu u P.

EXPTIME može da se reformuliše kao prostorna klasa APSPACE problema koji mogu biti rešeni primenom alternirajuće Tjuringove mašine u polinomijalnom prostoru. To jedan od načina da se vidi da je PSPACE $\subseteq$ EXPTIME, pošto je alternirajuća Tjuringova mašina najmanje jednako snažna kao i deterministička.

EXPTIME je samo jedna klasa u eksponencijalnoj hijerarhiji klasa složenosti sa sve složenijim oraklima ili kvantifikatorima alternacija. Klasa 2-EXPTIME je definisana slično kao EXPTIME samo sa dvostruko većom eksponencijalnom vremenskom granicom $2^{2^{n}}$. Ovo može da se generalizuje i na višestruke vremenske granice.

EXPTIME kompletnost

Problem odlučivanja je EXPTIME-kompletan, ako se nalazi u EXPTIME, i ako svaki problem u EXPTIME ima polinomijalno vremensko svođenje tipa više prema jedan na njega. Drugim rečima, postoji algoritam u polinomijalnom vremenu, koji transformiše instance jednog u instance drugog sa istim odgovorom. Problemi koji su EXPTIME kompletni mogu da se smatraju najtežim problemima u EXPTIME. Treba primetiti da iako ne znamo da li je ili ne NP jednako P, mi zanmo da EXPTIME kompletni problemi nisu u P. Teoremom o hijerarhiji vremena, dokazano je da ovi problemi ne mogu da se reše u polinomojalnom vremenu. Ostali primeri EXPTIME kompletnih problema uključuju probleme evaluacije pozicije o generalizovanom šahu , damama i igri Go (sa japanskim „ko“ pravilima). Ove igre imaju šansu da budu EXPTIME kompletne, zato što mogu da traju u broju poteza koji je eksponencijalan u odnosu na veličinu table. U primeru igre Go, japanska „ko“ pravila su dovoljno kruta da podrazumevaju EXPTIME kompletnost, ali se ne zna da li prilagodljivija američka ili kineska pravila obezbeđuju EXPTIME kompletnost. Nasuprot tome, generalizovane igre čiji je ukupan broj poteza polinomijalan u odnosu na veličinu table, su često PSPACE kompletne. Isto važi eksponencijalno duge igre u kojima je neponovljivost automatska. Poseban skup važnih EXPTIME kompletnih problema odnosi se na sažeta kola. Sažeta kola su jednostavne mašine koje se koriste za opis nekih grafova u eksponencijalno manjem prostoru. One prihvataju dva broja čvora kao ulazni i izlazni, ako postoji grana koja ih povezuje. Za mnoge P kompletne probleme grafova, gde se graf opisuje prirodnom reprezentacijom kao što je matrica povezanosti, rešavanje istog problema pomoću reprezentacije sažetog kola predstavlja EXPTIME kompletan problem zato što je ulaz eksponencijalno manji. Ali ovo zahteva netrivijalan dokaz, pošto sažeta kola mogu da opišu samo jednu podklasu grafova.

Literatura

• J. M. Robson (1983). „The complexity of Go”. Information Processing; Proceedings of IFIP Congress. str. 413—417.