EXPSPACE

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

${\displaystyle {\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 комплетног проблема је проблем препознавања да ли два регуларна израза представљају различите језике, где су изрази ограничени на четири оператора: унија, конкатенација, Клинијева звезда (нула или више копија једног израза) и квадрирање (две копије израза).^[1]

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