EXPSPACE

У рачунарској теорији сложености, EXPSPACE је скуп свих проблема одличивања решивих помоћу Тјурингове машине у простору O(2p(n)), где је p(n) полиномијална функција од n. (Неки аутори ограничавају p(n) да буде линеарна, али већина аутора називају резултујућу класу ESPACE). Ако користимо недетерминистичку машину добијамо класу NEXPSPACE која је по теореми Севича једнака EXPSPACE. У односу на DSPACE и NSPACE имамо:

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

Проблем одлучивања је комплетан, ако је у и сваки проблем из EXPSPACE. Проблем одлучивања је EXPSPACE -комплетан, ако се налази у EXPSPACE, и ако сваки проблем у EXPSPACE има полиномијални временски алгоритам који трансформише инстанце једног у инстанце другог са истим одговором.

Проблем одлучивања је EXPSPACE комплетан, ако се налази у EXPSPACE, и ако сваки проблем у EXPSPACE има полиномијално временско свођење типа више према један на њега. Другим речима, постоји алгоритам у полиномијалном времену, који трансформише инстанце једног у инстанце другог са истим одговором. Проблеми који су EXPSPACE комплетни могу да се сматрају најтежим проблемима у EXPSPACE.

EXPSPACE је строги надскуп PSPACE, NP, и P а верује се и да је строги надскуп EXPTIME. Пример једног EXPSPACE комплетног проблема је проблем препознавања да ли два регуларна израза представљају различите језике, где су изрази ограничени на четири оператора: унија, конкатенација, Клинијева звезда (нула или више копија једног израза) и квадрирање (две копије израза).

Ако би се Клинијева звезда оставила по страни проблем постаје NEXPTIME комплетан, што је слично EXPTIME комплетности, осим што је дефинисана у односу на недетерминистичку Тјурингову машину. Л. Берман је 1980. године, такође, показао да проблем верификације/фалсификације било ког исказа првог реда о реалним бројевима, који укључује сабирање и поређење (али не и множење) припада EXPSPACE.