Изворни код странице EXPSPACE

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

:<math>\mbox{EXPSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{DSPACE}(2^{n^k}) = \bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(2^{n^k})</math>

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

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

EXPSPACE је строги надскуп ''PSPACE'', ''NP'', и ''P'' а верује се и да је строги надскуп ''EXPTIME''.
Пример једног ''EXPSPACE'' комплетног проблема је проблем препознавања да ли два [[Regularni izraz|регуларна израза]] представљају различите језике, где су изрази ограничени на четири оператора: унија, конкатенација, Клинијева звезда (нула или више копија једног израза) и квадрирање (две копије израза).<ref>Meyer, A.R. and Larry Stockmeyer|L. Stockmeyer. [http://people.csail.mit.edu/meyer/rsq.pdf The equivalence problem for regular expressions with squaring requires exponential space]. ''13th IEEE Symposium on Switching and Automata Theory'', Oct (1972). стр. 125—129.</ref>

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

== Референце ==
{{reflist}}

{{нормативна контрола}}

[[Категорија:Класе комплексности]]