Exponential hierarchy
In computational complexity theory, the exponential hierarchy is a hierarchy of complexity classes, which is an exponential time analogue of the polynomial hierarchy. As elsewhere in complexity theory, “exponential” is used in two different meanings (linear exponential bounds for a constant c, and full exponential bounds ), leading to two versions of the exponential hierarchy:
* EH is the union of the classes for all k, where (i.e., languages computable in nondeterministic time for some constant c with a oracle). One also defines , . An equivalent definition is that a language L is in where , where ,
Exponential hierarchy
In computational complexity theory, the exponential hierarchy is a hierarchy of complexity classes, which is an exponential time analogue of the polynomial hierarchy. As elsewhere in complexity theory, “exponential” is used in two different meanings (linear exponential bounds for a constant c, and full exponential bounds ), leading to two versions of the exponential hierarchy:
* EH is the union of the classes for all k, where (i.e., languages computable in nondeterministic time for some constant c with a oracle). One also defines , . An equivalent definition is that a language L is in where , where ,
has abstract
Em teoria da complexidade comp ...... XPH ⊆ EXPSPACE, and EH ⊆ EXPH.
@pt
In computational complexity th ...... XPH ⊆ EXPSPACE, and EH ⊆ EXPH.
@en
Nella teoria della complessità ...... nziale è la classe ELEMENTARY.
@it
在計算複雜性理論內，指數譜系是一個複雜度類的分類層級(hie ...... 聯集，我們會得到一個大的複雜度類，名為ELEMENTARY。
@zh
Wikipage page ID
Wikipage revision ID
705,033,150
subject
comment
Em teoria da complexidade comp ...... utra definição , onde , onde ,
@pt
In computational complexity th ...... nguage L is in where , where ,
@en
Nella teoria della complessità ...... nziale è la classe ELEMENTARY.
@it
在計算複雜性理論內，指數譜系是一個複雜度類的分類層級(hie ...... 聯集，我們會得到一個大的複雜度類，名為ELEMENTARY。
@zh
label
Exponential hierarchy
@en
Gerarchia esponenziale
@it
Hierarquia exponencial
@pt
指數譜系
@zh