EXPTIME

En teoria de la complexitat, la classe de complexitat EXPTIME és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en temps O(2^p(n)), on p(n) és una funció polinomial sobre n.

En termes de DTIME es té

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

Es coneix que

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ EXPSPACE

i pel teorema de la jerarquia temporal:

P ⊂ EXPTIME

de manera que almenys una de les inclusions de la primera línia ha de ser estricta (es creu que totes ho son). També se sap que si P = NP, llavors EXPTIME = NEXPTIME, la classe de problemes resolubles amb temps exponencial per una màquina de Turing no determinista. En concret, EXPTIME ≠ NEXPTIME si i només si existeixen llenguatges escassos a NP que no estan a P.

La classe de complexitat EXPTIME-complet és la classe de problemes que estan a EXPTIME tals que tot problema d'EXPTIME té una transformació polinòmica cap a cada un dels problemes d'EXPTIME-complet. Dit d'una altra manera, existeix un algorisme que treballa en temps polinòmic que transforma les instàncies d'un problema en les instàncies de l'altra amb la mateixa resposta. El conjunt EXPTIME-complet pot esser vist com el conjunt de problemes més difícils d'EXPTIME.

Un exemple de problemes EXPTIME-complet són els de, a partir d'una posició dels escacs, dames o Go determinar si el primer jugador te una seqüència de jugades guanyadores. Aquests jocs son EXPTIME-complets, ja que la seqüència de jugades a partir d'una configuració donada és exponencial sobre la mida del tauler.