2-EXPTIME (original) (raw)
En informatique théorique, plus précisément en théorie de la complexité, la classe 2-EXPTIME est la classe des problèmes de décision décidés par une machine de Turing déterministe en temps doublement exponentiel, c'est-à-dire en temps O(22p(n)), où p(n) est un polynôme en la taille de l'entrée n. 2-EXPTIME est égale à la classe AEXPSPACE, la classe des problèmes décidés par une machine de Turing alternante en espace exponentiel.
| Property | Value |
|---|---|
| dbo:abstract | In computational complexity theory, the complexity class 2-EXPTIME (sometimes called 2-EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(22p(n)) time, where p(n) is a polynomial function of n. In terms of DTIME, We know P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE ⊆ 2-EXPTIME ⊆ ELEMENTARY. 2-EXPTIME can also be reformulated as the space class AEXPSPACE, the problems that can be solved by an alternating Turing machine in exponential space. This is one way to see that EXPSPACE ⊆ 2-EXPTIME, since an alternating Turing machine is at least as powerful as a deterministic Turing machine. 2-EXPTIME is one class in a hierarchy of complexity classes with increasingly higher time bounds. The class 3-EXPTIME is defined similarly to 2-EXPTIME but with a triply exponential time bound . This can be generalized to higher and higher time bounds. (en) En informatique théorique, plus précisément en théorie de la complexité, la classe 2-EXPTIME est la classe des problèmes de décision décidés par une machine de Turing déterministe en temps doublement exponentiel, c'est-à-dire en temps O(22p(n)), où p(n) est un polynôme en la taille de l'entrée n. 2-EXPTIME est égale à la classe AEXPSPACE, la classe des problèmes décidés par une machine de Turing alternante en espace exponentiel. (fr) Nella teoria della complessità computazionale, la classe di complessità 2-EXPTIME (talvolta chiamata 2-EXP, da 2-Exponential Time, "tempo 2-esponenziale") è l'insieme di tutti i problemi decisionali risolvibili da una macchina deterministica di Turing nel tempo O(22p(n)), dove p(n) è una funzione polinomiale di n. In termini di , Sappiamo che P NP PSPACE EXPTIME EXPSPACE 2-EXPTIME . 2-EXPTIME può anche essere riformulato come la classe di spazio AEXPSPACE, i problemi che possono essere risolti da una in spazio esponenziale. Questo è un modo di vedere che EXPSPACE 2-EXPTIME, dal momento che una macchina di Turing alternante è potente almeno quanto una macchina deterministica di Turing. 2-EXPTIME è una classe in una gerarchia esponenziale di classi di complessità con limiti temporali sempre più alti. La classe 3-EXPTIME è definita similmente a 2-EXPTIME, ma con un limite temporale triplamente esponenziale . Questo può essere generalizzato a limiti temporali sempre più alti. (it) Na teoria da Complexidade Computacional, a classe de complexidade 2-EXPTIME (também chamada 2-EXP) é o conjunto de todos os problemas de decisão solucionáveis por uma Máquina de Turing Determinística em tempo O(22p(n)), onde p(n) é uma função polinomial de n. Em termos de DTIME, Nós sabemos que: P NP PSPACE EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY. 2-EXPTIME também pode ser reformulado como a classe do espaço AEXPSPACE, os problemas que podem ser solucionados por uma Máquina de Turing Alternada em espaço exponencial. Esse é o único jeito para ver que EXPSPACE 2-EXPTIME, já que uma Máquina de Turing alternada é pelo menos tão poderosa quanto uma Máquina de Turing determinística. 2-EXPTIME é uma classe em uma hierarquia de classes de complexidade com crescente limite de tempo. a classe 3-EXPTIME é definida similarmente a 2-EXPTIME mas com limite de tempo exponencial triplo . Isso pode ser generalizado para cada vez maiores limites de tempos. (pt) 在計算複雜度理論內，2-EXPTIME這個複雜度類 (有時寫作2-EXP)是在O(22p(n))時間內，可以使用解決掉決定型問題的集合，這裡 p(n) 是n的一個多項式 用DTIME的方式說明， 我們已經知道 P NP PSPACE EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY. 2-EXPTIME也可以被重構成AEXPSPACE這個空間複雜度類(使用交替式圖靈機可以在指數空間內解決的問題)。因為交替式圖靈機至少有跟決定型圖靈機一樣的計算力，所以這也是一個看出EXPSPACE 2-EXPTIME的方式。 2-EXPTIME這個複雜度類，是在一種可以不斷提昇時間上限的複雜度類層級裡面的其中一類。像3-EXPTIME 這個類別，類似於2-EXPTIME的定義方式，可以用三倍指數時間限制 來定義。用同樣的方法可以定義出更高的時間上限(4-EXP，5-EXP…之類)。 (zh) |
| dbo:wikiPageID | 11387202 (xsd:integer) |
| dbo:wikiPageLength | 5862 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1106747501 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Quantifier_elimination dbr:NP_(complexity) dbr:Regular_expression dbr:Cylindrical_algebraic_decomposition dbr:DTIME dbr:Decision_problem dbr:Double_exponential_function dbr:EXPSPACE dbr:Presburger_arithmetic dbr:Worst-case_complexity dbr:Complement_(set_theory) dbr:Complexity_class dbr:Computation_tree_logic dbr:Computational_complexity_theory dbr:P_(complexity) dbr:ELEMENTARY dbr:EXPTIME dbr:Alternating_Turing_machine dbr:PSPACE dbc:Complexity_classes dbr:Gröbner_basis dbr:Big_O_notation dbr:Winning_strategy dbr:Real_closed_field dbr:Set_(mathematics) dbr:Partially_observable_system dbr:NEXPTIME dbr:Polynomial_Function dbr:Deterministic_Turing_machine |
| dbp:wikiPageUsesTemplate | dbt:ComplexityClasses |
| dcterms:subject | dbc:Complexity_classes |
| rdf:type | yago:WikicatComplexityClasses yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Group100031264 |
| rdfs:comment | En informatique théorique, plus précisément en théorie de la complexité, la classe 2-EXPTIME est la classe des problèmes de décision décidés par une machine de Turing déterministe en temps doublement exponentiel, c'est-à-dire en temps O(22p(n)), où p(n) est un polynôme en la taille de l'entrée n. 2-EXPTIME est égale à la classe AEXPSPACE, la classe des problèmes décidés par une machine de Turing alternante en espace exponentiel. (fr) 在計算複雜度理論內，2-EXPTIME這個複雜度類 (有時寫作2-EXP)是在O(22p(n))時間內，可以使用解決掉決定型問題的集合，這裡 p(n) 是n的一個多項式 用DTIME的方式說明， 我們已經知道 P NP PSPACE EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY. 2-EXPTIME也可以被重構成AEXPSPACE這個空間複雜度類(使用交替式圖靈機可以在指數空間內解決的問題)。因為交替式圖靈機至少有跟決定型圖靈機一樣的計算力，所以這也是一個看出EXPSPACE 2-EXPTIME的方式。 2-EXPTIME這個複雜度類，是在一種可以不斷提昇時間上限的複雜度類層級裡面的其中一類。像3-EXPTIME 這個類別，類似於2-EXPTIME的定義方式，可以用三倍指數時間限制 來定義。用同樣的方法可以定義出更高的時間上限(4-EXP，5-EXP…之類)。 (zh) In computational complexity theory, the complexity class 2-EXPTIME (sometimes called 2-EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(22p(n)) time, where p(n) is a polynomial function of n. In terms of DTIME, We know P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE ⊆ 2-EXPTIME ⊆ ELEMENTARY. 2-EXPTIME is one class in a hierarchy of complexity classes with increasingly higher time bounds. The class 3-EXPTIME is defined similarly to 2-EXPTIME but with a triply exponential time bound . This can be generalized to higher and higher time bounds. (en) Nella teoria della complessità computazionale, la classe di complessità 2-EXPTIME (talvolta chiamata 2-EXP, da 2-Exponential Time, "tempo 2-esponenziale") è l'insieme di tutti i problemi decisionali risolvibili da una macchina deterministica di Turing nel tempo O(22p(n)), dove p(n) è una funzione polinomiale di n. In termini di , Sappiamo che P NP PSPACE EXPTIME EXPSPACE 2-EXPTIME . (it) Na teoria da Complexidade Computacional, a classe de complexidade 2-EXPTIME (também chamada 2-EXP) é o conjunto de todos os problemas de decisão solucionáveis por uma Máquina de Turing Determinística em tempo O(22p(n)), onde p(n) é uma função polinomial de n. Em termos de DTIME, Nós sabemos que: P NP PSPACE EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY. (pt) |
| rdfs:label | 2-EXPTIME (en) 2-EXPTIME (fr) 2-EXPTIME (it) 2-EXPTIME (pt) 2-EXPTIME (zh) |
| owl:sameAs | freebase:2-EXPTIME yago-res:2-EXPTIME wikidata:2-EXPTIME dbpedia-fr:2-EXPTIME dbpedia-it:2-EXPTIME dbpedia-pt:2-EXPTIME dbpedia-zh:2-EXPTIME https://global.dbpedia.org/id/A7Di |
| prov:wasDerivedFrom | wikipedia-en:2-EXPTIME?oldid=1106747501&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:2-EXPTIME |
| is dbo:wikiPageRedirects of | dbr:2-EXP dbr:2EXPTIME |
| is dbo:wikiPageWikiLink of | dbr:List_of_complexity_classes dbr:Double_exponential_function dbr:Time_complexity dbr:Linear_temporal_logic dbr:EXPTIME dbr:2-EXP dbr:2EXPTIME |
| is foaf:primaryTopic of | wikipedia-en:2-EXPTIME |