| rdfs:comment
| - في نظرية التعقيد EXPTIME أو EXP للاختصار هي مجموعة مسائل التي يمكن حلها بوقت أُسي بواسطة آلة تورنغ حتمية. (ar)
- In der Komplexitätstheorie steht EXPTIME (manchmal auch nur EXP) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer deterministischen Turingmaschine (DTM) in durch beschränkter Zeit entschieden werden können. ist dabei ein beliebiges Polynom in der Eingabelänge . In der DTIME-Notation ausgedrückt gilt also: (de)
- En théorie de la complexité, EXPTIME (ou EXP) est la classe de complexité qui est l'ensemble des problèmes de décision décidés par une machine de Turing déterministe en temps exponentiel. (fr)
- Класс сложности EXPTIME (иногда называемый просто EXP) — это множество задач, в теории сложности вычислений, решаемых с помощью детерминированной машины Тьюринга за время O(2p(n)), где p(n) это полиномиальная функция от n. (ru)
- Експоненціальний алгоритм, EXPTIME (від англ. Exponential Time — експоненційний час) — в теорії складності обчислень, клас задач, які розв'язні на машині Тюринга за час O(2p(n))), де p(n) — поліноміальна функція від n. (uk)
- 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(2p(n)), on p(n) és una funció polinomial sobre n. En termes de DTIME es té Es coneix que P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ EXPSPACE i pel teorema de la jerarquia temporal: P ⊂ EXPTIME (ca)
- In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that are solvable by a deterministic Turing machine in exponential time, i.e., in O(2p(n)) time, where p(n) is a polynomial function of n. EXPTIME is one intuitive class in an exponential hierarchy of complexity classes with increasingly more complex oracles or quantifier alternations. For example, the class 2-EXPTIME is defined similarly to EXPTIME but with a doubly exponential time bound. This can be generalized to higher and higher time bounds. (en)
- En teoría de la complejidad computacional, la clase de complejidad EXPTIME (también llamada EXP) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(2p(n)), donde p(n) es una función polinomial sobre n. En términos de DTIME, Se sabe que P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ EXPSPACE y por el teorema de la jerarquía temporal: P ⊂ EXPTIME de manera que al menos una de las inclusiones de la primera línea debe ser estricta (se piensa que todas esas inclusiones son estrictas). (es)
- Nella teoria della complessità computazionale la classe di complessità EXPTIME (a volte chiamata EXP, da Exponential Time, "tempo esponenziale"), è l'insieme di tutti i problemi decisionali risolvibili da una macchina deterministica di Turing nel tempo O(2p(n)), dove p(n) è una funzione polinomiale di n. In termini di , Sappiamo che P NP PSPACE EXPTIME EXPSPACE e inoltre, dal e dal , che P EXPTIME e NP NEXPTIME e PSPACE EXPSPACE (it)
- EXPTIME（EXPとも）は、計算量理論において、チューリング機械で O(2p(n)) の時間で解ける全ての決定問題の集合である。なお、p(n) は n の多項式関数である。 DTIMEでは次のように表される。 以下の関係が知られている。 P NP PSPACE EXPTIME NEXPTIME EXPSPACE また、とにより、次のようになる。 P EXPTIME かつ NP NEXPTIME かつ PSPACE EXPSPACE 従って、包含関係の最初の3つのうち少なくとも1つが真部分集合の関係であり、後半3つのうち少なくとも1つが真部分集合の関係にある。ただし、どれがそうなのかは分かっていない。多くの研究者は上記の全てが真部分集合の関係であると考えている。また、P = NP であれば EXPTIME = NEXPTIME となることが分かっている。NEXPTIME は非決定性チューリング機械で指数関数時間で解ける問題のクラスである。 EXPTIME は空間（領域）のクラス APSPACE にも等しい。APSPACE は交替性チューリング機械で多項式領域で解ける問題のクラスである。交替性チューリング機械は決定性チューリング機械と少なくとも同程度に強力であるので、これによっても PSPACE EXPTIME が示される。 (ja)
- 계산 복잡도 이론에서 복잡도 종류 EXPTIME(EXP라고도 한다)은 결정론적 튜링 기계가 시간에 풀 수 있는 모든 판정 문제의 집합이다. 여기서 은 에 대한 다항함수이다. 에 대한 식으로 정리하면 이렇다: 다음과 같은 사실이 알려져 있다. P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ ⊆ EXPSPACE 또한, 와 에 따르면 아래와 같다. P EXPTIME 이고 NP NEXPTIME 이고 PSPACE EXPSPACE이다 따라서 앞쪽 세 포함관계 중 적어도 하나는 진부분집합이어야 한다. 뒤쪽 세 포함관계도 마찬가지이다. 그러나 어느 것이 진부분집합 관계인지는 알려져 있지 않다. 전문가들은 모든 포함관계가 진부분집합 관계일 것으로 보고 있다. 만약 P = NP라면 EXPTIME = 이 성립한다는 사실도 알려져 있다. NEXPTIME은 비결정론적 튜링 기계가 지수 시간에 풀 수 있는 문제의 집합이다. 더 정확히 말하면, EXPTIME ≠ NEXPTIME이고 오직 그럴 때만 NP 중에 P가 아닌 가 존재한다. (ko)
- W obliczeniowej teorii złożoności klasa złożoności EXPTIME (czasami nazywana EXP lub DEXPTIME) jest zbiorem wszystkich problemów decyzyjnych, które mają wykładniczy czas wykonywania, tj. są rozwiązywalne przez deterministyczną maszynę Turinga w czasie O (2p(n)), gdzie p(n) jest funkcją wielomianową n. Definicja używająca DTIME: Wiemy, że: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE, a także według twierdzenia o hierarchii czasu i twierdzenia o hierarchii przestrzeni, że P ⊊ EXPTIME, NP ⊊ NEXPTIME and PSPACE ⊊ EXPSPACE, (pl)
- Na teoria da complexidade computacional, a classe de complexidade Exptime (às vezes chamado EXP) é o conjunto de todos os problemas de decisão solúveis por uma máquina de Turing determinística em O(2p(n)) tempo, onde p (n) é uma função polinomial de n. Em termos de DTIME, Sabemos que P NP PSPACE EXPTIME NEXPTIME EXPSPACE e também, pelo time hierarchy theoremeo space hierarchy theorem, que P EXPTIME and NP NEXPTIME and PSPACE EXPSPACE (pt)
- 在計算複雜性理論裡面，EXPTIME（有時稱作EXP）這個複雜度類是一些決定型問題的集合，這些問題可以使用圖靈機在O(2p(n))的時間內解決，這裡的p(n)代表的是n的某個多項式。 用DTIME來定義，則是 我們已經知道 P NP PSPACE EXPTIME NEXPTIME EXPSPACE 另外，根據時間譜系理論（time hierarchy theorem）以及（space hierarchy theorem）， P EXPTIME 且 NP NEXPTIME 且 PSPACE EXPSPACE 所以至少第一條包含關係中，前三個包含關係中的一個，以及後三個包含關係中的一個，必然是完整包含（沒有相等可能），但是我們還不知道那一個是。多數人相信這一些複雜度類全部都不相等。另外我們已知如果P = NP，則EXPTIME = NEXPTIME，這裡的NEXPTIME是在指數時間內可以使用非確定型圖靈機解決的問題。更精確的說，EXPTIME ≠ NEXPTIME若且唯若存在一個稀疏語言，在NP裡面且不在P內。 EXPTIME也可以用空間的方式來定義，等同於APSPACE這個複雜度類。APSPACE的意思是包含了所有可以用交替式圖靈機在多項式空間內解決的問題。這種定義方式也是一種看出PSPACE EXPTIME的方式，因為已知交替式圖靈機至少跟確定型圖靈機計算能力一樣。 (zh)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)