EXPSPACE

U računarskoj teoriji složenosti, EXPSPACE je skup svih problema odličivanja rešivih pomoću Tjuringove mašine u prostoru O(2p(n)), gde je p(n) polinomijalna funkcija od n. (Neki autori ograničavaju p(n) da bude linearna, ali većina autora nazivaju rezultujuću klasu ESPACE). Ako koristimo nedeterminističku mašinu dobijamo klasu NEXPSPACE koja je po teoremi Seviča jednaka EXPSPACE. U odnosu na DSPACE i NSPACE imamo:

${\mbox{EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}(2^{n^{k}})=\bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}(2^{n^{k}})$

Problem odlučivanja je kompletan, ako je u i svaki problem iz EXPSPACE. Problem odlučivanja je EXPSPACE -kompletan, ako se nalazi u EXPSPACE, i ako svaki problem u EXPSPACE ima polinomijalni vremenski algoritam koji transformiše instance jednog u instance drugog sa istim odgovorom.

Problem odlučivanja je EXPSPACE kompletan, ako se nalazi u EXPSPACE, i ako svaki problem u EXPSPACE 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 EXPSPACE kompletni mogu da se smatraju najtežim problemima u EXPSPACE.

EXPSPACE je strogi nadskup PSPACE, NP, i P a veruje se i da je strogi nadskup EXPTIME. Primer jednog EXPSPACE kompletnog problema je problem prepoznavanja da li dva regularna izraza predstavljaju različite jezike, gde su izrazi ograničeni na četiri operatora: unija, konkatenacija, Klinijeva zvezda (nula ili više kopija jednog izraza) i kvadriranje (dve kopije izraza).

Ako bi se Klinijeva zvezda ostavila po strani problem postaje NEXPTIME kompletan, što je slično EXPTIME kompletnosti, osim što je definisana u odnosu na nedeterminističku Tjuringovu mašinu. L. Berman je 1980. godine, takođe, pokazao da problem verifikacije/falsifikacije bilo kog iskaza prvog reda o realnim brojevima, koji uključuje sabiranje i poređenje (ali ne i množenje) pripada EXPSPACE.