Back

ⓘ EXPSPACE




                                     

ⓘ EXPSPACE

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

EXPSPACE = ⋃ k ∈ N DSPACE 2 n k = ⋃ k ∈ N NSPACE 2 n k {\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 комплетног проблема је проблем препознавања да ли два регуларна израза представљају различите језике, где су изрази ограничени на четири оператора: унија, конкатенација, Клинијева звезда нула или више копија једног израза и квадрирање две копије израза.

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

                                     
  • контекстно - сензитиван је било који рекурзиван језик чије је одлучивање EXPSPACE - тежак проблем, на пример, скуп парова еквивалентних регуларних израза са

Users also searched:

...