Exponential hierarchy (original) (raw)
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. This hierarchy is sometimes also referred to as the weak exponential hierarchy, to differentiate it from the strong exponential hierarchy.
| Property | Value |
|---|---|
| dbo:abstract | En teoria de la complexitat, la jerarquia exponencial és una jerarquia de classes de complexitat que es l'anàloga a la jerarquia polinòmica amb temps exponencial. En aquest camp, el mot exponencial es fa servir en dos concepte diferents: fites exponencials lineals 2cn per una c constant i límits exponencials , donant dues versions de la jerarquia exponencial: * EH és la unió de les classes per tot k, on (llenguatges computables en una màquina de Turing no determinista en temps 2cn per alguna constant c amb un oracle ). Es defineix també . Una definició equivalent és que un llenguatge L és a si i només si es pot escriure de la forma:on és un predicat computable en temps . També i de forma equivalent, EH és la classe dels llenguatges computables amb una màquina de Turing alternant en temps per algun c. * EHPH és la unió de les classes , on (llenguatges computables en una màquina de Turing no determinista en temps per alguna constant c amb un oracle ).Es defineix també . Una definició equivalent és que un llenguatge L és a si i només si es pot escriure de la forma:on és un predicat computable en temps . També i de forma equivalent, EXPH és la classe dels llenguatges computables amb una màquina de Turing alternant en temps per algun c. Es te que E ⊆ NE ⊆ ⊆ , EXP ⊆ NEXP ⊆ EXPH ⊆ EXPSPACE, i EH ⊆ EXPH. (ca) 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. This hierarchy is sometimes also referred to as the weak exponential hierarchy, to differentiate it from the strong exponential hierarchy. (en) Nella teoria della complessità computazionale, la gerarchia esponenziale è una gerarchia di classi di complessità, che inizia con EXPTIME: e continua con e così via. Abbiamo P ⊂ EXPTIME ⊂ 2-EXPTIME ⊂ 3-EXPTIME ⊂ …. Diversamente dal caso analogo della , il garantisce che queste inclusioni sono corrette; cioè, che vi sono linguaggi in EXPTIME ma non P, in 2-EXPTIME ma non in EXPTIME e così via. L'unione di tutte le classi nella gerarchia esponenziale è la classe . (it) Em teoria da complexidade computacional, a hierarquia exponencial é a hierarquia da , que pertencem à classe de tempo exponencial, análogo a hierarquia polinomial. Como em outros lugares da teoria da complexidade, "exponencial" é usado em dois contextos diferentes (limite exponencial linear para uma constante c, e limite exponencial completo ), levando a duas versões diferentes da hierarquia exponencial: * EH é a união das classes para todo k, onde (i.e, linguagens computáveis em tempo para alguma constante c com oráculo . Uma outra definição , . Uma definição equivalente é que a linguagem L está em se e somente se ela pode ser escrita na formaonde é um predicado computável em tempo ( o que implicitamente limita o comprimento de yi). Também equivalente, EH é a classe de linguagens computáveis em uma em tempo para algum c com constantes alterações. * EXPH é a união das classes , onde (linguagens computáveis em tempo não determinístico para alguma constante c com oráculo ), e novamente , . A linguagem L está em se e somente se puder ser escrita na forma:onde é computável em tempo para algum c, que novamente possui limites implícitos de comprimento yi. Equivalentemente, EXPH é a classe de linguagens computáveis em tempo em uma máquina de turing alternante com constantes alternâncias.Temos ⊆ ⊆ EH ⊆ ESPACE, EXP ⊆ NEXP ⊆ EXPH ⊆ EXPSPACE, and EH ⊆ EXPH. (pt) 在計算複雜性理論內，指數譜系是一個複雜度類的分類層級(hierarchy)，以EXPTIME開始： 然後接著 ，以下雷同。 我們已知P ⊂ EXPTIME ⊂ 2-EXPTIME ⊂ 3-EXPTIME ⊂ …。跟相類似的多項式譜系不同，時間譜系理論(Time hierarchy theorem)保證了這列關係都是真子集(proper)，意思是，存在語言在EXPTIME而不在P內，也存在語言在2-EXPTIME但不在EXPTIME內，以下類推。 將所有指數譜系的複雜度類作聯集，我們會得到一個大的複雜度類，名為ELEMENTARY。 (zh) |
| dbo:wikiPageID | 665091 (xsd:integer) |
| dbo:wikiPageLength | 3544 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1056524472 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:NE_(complexity) dbr:Nondeterministic_Turing_machine dbr:ESPACE dbr:EXPSPACE dbr:Complexity_class dbr:Computational_complexity_theory dbr:EXPTIME dbr:E_(complexity) dbr:Alternating_Turing_machine dbc:Complexity_classes dbr:Polynomial_hierarchy dbr:NEXPTIME dbr:Oracle_Turing_machine |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:ComplexityClasses dbt:CZoo |
| dct:subject | dbc:Complexity_classes |
| rdf:type | yago:WikicatComplexityClasses yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Group100031264 |
| rdfs:comment | 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. This hierarchy is sometimes also referred to as the weak exponential hierarchy, to differentiate it from the strong exponential hierarchy. (en) Nella teoria della complessità computazionale, la gerarchia esponenziale è una gerarchia di classi di complessità, che inizia con EXPTIME: e continua con e così via. Abbiamo P ⊂ EXPTIME ⊂ 2-EXPTIME ⊂ 3-EXPTIME ⊂ …. Diversamente dal caso analogo della , il garantisce che queste inclusioni sono corrette; cioè, che vi sono linguaggi in EXPTIME ma non P, in 2-EXPTIME ma non in EXPTIME e così via. L'unione di tutte le classi nella gerarchia esponenziale è la classe . (it) 在計算複雜性理論內，指數譜系是一個複雜度類的分類層級(hierarchy)，以EXPTIME開始： 然後接著 ，以下雷同。 我們已知P ⊂ EXPTIME ⊂ 2-EXPTIME ⊂ 3-EXPTIME ⊂ …。跟相類似的多項式譜系不同，時間譜系理論(Time hierarchy theorem)保證了這列關係都是真子集(proper)，意思是，存在語言在EXPTIME而不在P內，也存在語言在2-EXPTIME但不在EXPTIME內，以下類推。 將所有指數譜系的複雜度類作聯集，我們會得到一個大的複雜度類，名為ELEMENTARY。 (zh) En teoria de la complexitat, la jerarquia exponencial és una jerarquia de classes de complexitat que es l'anàloga a la jerarquia polinòmica amb temps exponencial. En aquest camp, el mot exponencial es fa servir en dos concepte diferents: fites exponencials lineals 2cn per una c constant i límits exponencials , donant dues versions de la jerarquia exponencial: Es te que E ⊆ NE ⊆ ⊆ , EXP ⊆ NEXP ⊆ EXPH ⊆ EXPSPACE, i EH ⊆ EXPH. (ca) Em teoria da complexidade computacional, a hierarquia exponencial é a hierarquia da , que pertencem à classe de tempo exponencial, análogo a hierarquia polinomial. Como em outros lugares da teoria da complexidade, "exponencial" é usado em dois contextos diferentes (limite exponencial linear para uma constante c, e limite exponencial completo ), levando a duas versões diferentes da hierarquia exponencial: (pt) |
| rdfs:label | Jerarquia exponencial (ca) Exponential hierarchy (en) Gerarchia esponenziale (it) Hierarquia exponencial (pt) 指數譜系 (zh) |
| owl:sameAs | freebase:Exponential hierarchy yago-res:Exponential hierarchy wikidata:Exponential hierarchy dbpedia-ca:Exponential hierarchy dbpedia-it:Exponential hierarchy dbpedia-pt:Exponential hierarchy dbpedia-zh:Exponential hierarchy https://global.dbpedia.org/id/3UPBj |
| prov:wasDerivedFrom | wikipedia-en:Exponential_hierarchy?oldid=1056524472&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Exponential_hierarchy |
| is dbo:wikiPageDisambiguates of | dbr:EH |
| is dbo:wikiPageRedirects of | dbr:EXPH |
| is dbo:wikiPageWikiLink of | dbr:List_of_complexity_classes dbr:List_of_computability_and_complexity_topics dbr:List_of_mathematical_logic_topics dbr:Presburger_arithmetic dbr:EXPTIME dbr:List_of_exponential_topics dbr:EH dbr:Polynomial_hierarchy dbr:Time_hierarchy_theorem dbr:EXPH |
| is foaf:primaryTopic of | wikipedia-en:Exponential_hierarchy |