EXPTIME
In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that have exponential runtime, i.e., that are solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. In terms of DTIME, We know P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE and also, by the time hierarchy theorem and the space hierarchy theorem, that P ⊊ EXPTIME, NP ⊊ NEXPTIME and PSPACE ⊊ EXPSPACE . This can be generalized to higher and higher time bounds.
Wikipage disambiguates
primaryTopic
EXPTIME
In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that have exponential runtime, i.e., that are solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. In terms of DTIME, We know P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE and also, by the time hierarchy theorem and the space hierarchy theorem, that P ⊊ EXPTIME, NP ⊊ NEXPTIME and PSPACE ⊊ EXPSPACE . This can be generalized to higher and higher time bounds.
has abstract
EXPTIME (ou EXP) est une class ...... rministe en temps exponentiel.
@fr
EXPTIME(EXPとも)は、計算量理論において、チューリ ...... これを一般化していけば様々な時間計算量のクラスが定義される。
@ja
En teoría de la complejidad co ...... generalmente PSPACE-completo.)
@es
In computational complexity th ...... higher and higher time bounds.
@en
In der Komplexitätstheorie ste ...... otation ausgedrückt gilt also:
@de
Na teoria da complexidade comp ...... de tempo cada vez mais altos.
@pt
Nella teoria della complessità ...... iti temporali sempre più alti.
@it
В теории сложности вычислений, ...... о полиномиальная функция от n.
@ru
في نظرية التعقيد EXPTIME أو EX ...... أُسي بواسطة آلة تورنج حتمية .
@ar
在計算複雜性理論裡面,EXPTIME(有時稱作EXP)這個複 ...... ion)的時間限制 。使用類似方式可以類推出更高的時間上限。
@zh
Wikipage page ID
Wikipage revision ID
742,310,238
subject
comment
EXPTIME (ou EXP) est une class ...... rministe en temps exponentiel.
@fr
EXPTIME(EXPとも)は、計算量理論において、チューリ ...... 、これによっても PSPACE EXPTIME が示される。
@ja
En teoría de la complejidad co ...... as inclusiones son estrictas).
@es
In computational complexity th ...... higher and higher time bounds.
@en
In der Komplexitätstheorie ste ...... otation ausgedrückt gilt also:
@de
Na teoria da complexidade comp ...... XPTIME and PSPACE EXPSPACE
@pt
Nella teoria della complessità ...... iti temporali sempre più alti.
@it
В теории сложности вычислений, ...... о полиномиальная функция от n.
@ru
في نظرية التعقيد EXPTIME أو EX ...... أُسي بواسطة آلة تورنج حتمية .
@ar
在計算複雜性理論裡面,EXPTIME(有時稱作EXP)這個複 ...... 的方式,因為已知交替式圖靈機至少跟確定型圖靈機計算能力一樣。
@zh
label
EXPTIME
@ar
EXPTIME
@de
EXPTIME
@en
EXPTIME
@es
EXPTIME
@fr
EXPTIME
@it
EXPTIME
@ja
EXPTIME
@zh
Exptime
@pt
Класс EXPTIME
@ru