EXPTIME

У рачунарској теорији сложености, класа сложености EXPTIME која се повремено назива EXP или DEXPTIME, је скуп свих проблема одлучивања који имају експоненцијално време извршења, т.ј., који су решиви помоћу детерминистичке Тјурингове машине у O(2^p(n)) времену, где је p(n) полиномијална функција од n. У терминима DTIME:

${\mbox{EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{ DTIME }}\left(2^{n^{k}}\right).$

Знамо да важи:

P $\subseteq$ NP $\subseteq$ PSPACE $\subseteq$ EXPTIME $\subseteq$ NEXPTIME $\subseteq$ EXPSPACE

а према теоремама о хијерархији времена и простора, да је:

P $\subsetneq$ EXPTIME   and   NP $\subsetneq$ NEXPTIME   and   PSPACE $\subsetneq$ EXPSPACE

Тако, барем једна од прве три инклузије и барем једна од друге три приказане инклузије морају да буду правилне, али није познато које. Већина стручњака верује да су све инклузије правилне. Такође је познато да, ако је P = NP, важи и да је EXPTIME = NEXPTIME, класи проблема решивих у експоненцијалном времену на недетерминистичкој Тјуринговој машини. Тачније EXPTIME ≠ NEXPTIME, ако и само ако постоје оскудни језици (sparse languages) у NP који нису у P.

EXPTIME може да се реформулише као просторна класа APSPACE проблема који могу бити решени применом алтернирајуће Тјурингове машине у полиномијалном простору. То један од начина да се види да је PSPACE $\subseteq$ EXPTIME, пошто је алтернирајућа Тјурингова машина најмање једнако снажна као и детерминистичка.

EXPTIME је само једна класа у експоненцијалној хијерархији класа сложености са све сложенијим ораклима или квантификаторима алтернација. Класа 2-EXPTIME је дефинисана слично као EXPTIME само са двоструко већом експоненцијалном временском границом $2^{2^{n}}$. Ово може да се генерализује и на вишеструке временске границе.

EXPTIME комплетност

Проблем одлучивања је EXPTIME-комплетан, ако се налази у EXPTIME, и ако сваки проблем у EXPTIME има полиномијално временско свођење типа више према један на њега. Другим речима, постоји алгоритам у полиномијалном времену, који трансформише инстанце једног у инстанце другог са истим одговором. Проблеми који су EXPTIME комплетни могу да се сматрају најтежим проблемима у EXPTIME. Треба приметити да иако не знамо да ли је или не NP једнако P, ми занмо да EXPTIME комплетни проблеми нису у P. Теоремом о хијерархији времена, доказано је да ови проблеми не могу да се реше у полиномојалном времену. Остали примери EXPTIME комплетних проблема укључују проблеме евалуације позиције о генерализованом шаху , дамама и игри Го (са јапанским „ко“ правилима). Ове игре имају шансу да буду EXPTIME комплетне, зато што могу да трају у броју потеза који је експоненцијалан у односу на величину табле. У примеру игре Го, јапанска „ко“ правила су довољно крута да подразумевају EXPTIME комплетност, али се не зна да ли прилагодљивија америчка или кинеска правила обезбеђују EXPTIME комплетност. Насупрот томе, генерализоване игре чији је укупан број потеза полиномијалан у односу на величину табле, су често PSPACE комплетне. Исто важи експоненцијално дуге игре у којима је непоновљивост аутоматска. Посебан скуп важних EXPTIME комплетних проблема односи се на сажета кола. Сажета кола су једноставне машине које се користе за опис неких графова у експоненцијално мањем простору. Оне прихватају два броја чвора као улазни и излазни, ако постоји грана која их повезује. За многе P комплетне проблеме графова, где се граф описује природном репрезентацијом као што је матрица повезаности, решавање истог проблема помоћу репрезентације сажетог кола представља EXPTIME комплетан проблем зато што је улаз експоненцијално мањи. Али ово захтева нетривијалан доказ, пошто сажета кола могу да опишу само једну подкласу графова.

Литература

• J. M. Robson (1983). „The complexity of Go”. Information Processing; Proceedings of IFIP Congress. стр. 413—417.