| dbo:abstract
|
- في نظرية التعقيد EXPTIME أو EXP للاختصار هي مجموعة مسائل التي يمكن حلها بوقت أُسي بواسطة آلة تورنغ حتمية. (ar)
- 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 de manera que almenys una de les inclusions de la primera línia ha de ser estricta (es creu que totes ho son). També se sap que si P = NP, llavors EXPTIME = NEXPTIME, la classe de problemes resolubles amb temps exponencial per una màquina de Turing no determinista. En concret, EXPTIME ≠ NEXPTIME si i només si existeixen llenguatges escassos a NP que no estan a P. La classe de complexitat EXPTIME-complet és la classe de problemes que estan a EXPTIME tals que tot problema d'EXPTIME té una transformació polinòmica cap a cada un dels problemes d'EXPTIME-complet. Dit d'una altra manera, existeix un algorisme que treballa en temps polinòmic que transforma les instàncies d'un problema en les instàncies de l'altra amb la mateixa resposta. El conjunt EXPTIME-complet pot esser vist com el conjunt de problemes més difícils d'EXPTIME. Un exemple de problemes EXPTIME-complet son els de, a partir d'una posició dels escacs, dames o Go determinar si el primer jugador te una seqüència de jugades guanyadores. Aquests jocs son EXPTIME-complets, ja que la seqüència de jugades a partir d'una configuració donada és exponencial sobre la mida del tauler. (ca)
- 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)
- 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. EXPTIME can also be reformulated as the space class APSPACE, the set of all problems that can be solved by an alternating Turing machine in polynomial space. EXPTIME relates to the other basic time and space complexity classes in the following way: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE. Furthemore, by the time hierarchy theorem and the space hierarchy theorem, it is known that P ⊊ EXPTIME, NP ⊊ NEXPTIME and PSPACE ⊊ EXPSPACE. (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). La clase de complejidad EXPTIME-completo es el conjunto de problemas de decisión que están en EXPTIME tales que todo problema de EXPTIME tiene una transformación polinomial hacia cada uno de los problemas de EXPTIME-completo. Dicho de otra forma, existe un algoritmo que trabaja en tiempo polinómico que transforma las instancias de un problema en las instancias del otro con la misma respuesta. El conjunto EXPTIME-completo puede ser visto como el conjunto de los problemas más difíciles de EXPTIME. Como ejemplos de problemas EXPTIME-completos están el buscar a partir de una posición (en una versión generalizada) del Ajedrez, Damas, o Go y determinar si el primer jugador tiene una secuencia de jugadas ganadora a partir de allí. Estos juegos son EXPTIME-completos dado que las secuencias de jugadas a partir de una configuración dada es exponencial sobre el tamaño del tablero. (Cuando se tiene un juego generalizado en el cual el número de jugadas a partir de una configuración es polinómico en el tamaño del tablero, el mismo problema resulta generalmente PSPACE-completo.) (es)
- 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라고도 한다)은 결정론적 튜링 기계가 시간에 풀 수 있는 모든 판정 문제의 집합이다. 여기서 은 에 대한 다항함수이다. 에 대한 식으로 정리하면 이렇다: 다음과 같은 사실이 알려져 있다. P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ ⊆ EXPSPACE 또한, 와 에 따르면 아래와 같다. P EXPTIME 이고 NP NEXPTIME 이고 PSPACE EXPSPACE이다 따라서 앞쪽 세 포함관계 중 적어도 하나는 진부분집합이어야 한다. 뒤쪽 세 포함관계도 마찬가지이다. 그러나 어느 것이 진부분집합 관계인지는 알려져 있지 않다. 전문가들은 모든 포함관계가 진부분집합 관계일 것으로 보고 있다. 만약 P = NP라면 EXPTIME = 이 성립한다는 사실도 알려져 있다. NEXPTIME은 비결정론적 튜링 기계가 지수 시간에 풀 수 있는 문제의 집합이다. 더 정확히 말하면, EXPTIME ≠ NEXPTIME이고 오직 그럴 때만 NP 중에 P가 아닌 가 존재한다. EXPTIME은 교대 튜링 기계가 다항 공간을 써서 풀 수 있는 문제들의 집합인 로 다시 쓸 수 있다. 이것은 PSPACE ⊆ EXPTIME임을 보이는 방법이기도 하다. 교대 튜링 기계는 최소한 결정 튜링 기계보다는 강력하기 때문이다. (ko)
- 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 così almeno una delle prime tre inclusioni e almeno una delle ultime tre inclusioni deve essere corretta, ma non si sa quali sono, anche se la maggior parte degli esperti credono che tutte le inclusioni siano corrette. Si sa anche che se , allora EXPTIME = , la classe dei problemi risolvibili nel tempo esponenziale da una macchina di Turing non deterministica. Più precisamente, EXPTIME ≠ NEXPTIME se e solo se esistono in NP che non sono in P. EXPTIME può anche essere riformulato come la classe di spazio , i problemi che possono essere risolti da una nello spazio polinomiale. Questo è un modo di vedere che PSPACE EXPTIME, poiché una macchina di Turing alternante è potente almeno quanto una macchina di Turing deterministica. EXPTIME è una classe in una gerarchia esponenziale di classi di complessità con limiti temporali sempre più alti. La classe 2-EXPTIME è definita similmente a EXPTIME, ma con un limite temporale doppiamente esponenziale . Questo può essere generalizzato a limiti temporali sempre più alti. (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 が示される。 EXPTIME は時間計算量に関する階層の一部となっている。 クラスは EXPTIME と似ているが、二重指数時間 かかる問題のクラスである。これを一般化していけば様々な時間計算量のクラスが定義される。 (ja)
- Класс сложности EXPTIME (иногда называемый просто EXP) — это множество задач, в теории сложности вычислений, решаемых с помощью детерминированной машины Тьюринга за время O(2p(n)), где p(n) это полиномиальная функция от n. (ru)
- 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, więc co najmniej jedna z pierwszych trzech inkluzji i co najmniej jedna z trzech ostatnich inkluzji muszą być właściwe, ale nie wiadomo, które z nich są. Większość ekspertów uważa, że wszystkie inkluzje są prawidłowe. Wiadomo również, że jeśli P = NP, to EXPTIME = NEXPTIME, klasa problemów możliwych do rozwiązania w czasie wykładniczym przez niedeterministyczną maszynę Turinga. Dokładniej, EXPTIME ≠ NEXPTIME wtedy i tylko wtedy, gdy istnieją rzadkie języki w NP, które nie są w P. EXPTIME można również przeformułować jako klasę przestrzeni APSPACE, problemy, które można rozwiązać za pomocą naprzemiennej maszyny Turinga w przestrzeni wielomianowej. Jest to jeden ze sposobów, aby zobaczyć PSPACE ⊆ EXPTIME, ponieważ naprzemienna maszyna Turinga jest co najmniej tak potężna jak deterministyczna maszyna Turinga. (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 assim pelo menos uma das três primeiras inclusões e pelo menos uma das três últimas inclusões deve ser adequada, mas não se sabe quais são. A maioria dos especialistas acreditam que todas as inclusões são próprias. É também conhecido que, se P = NP, então EXPTIME = NEXPTIME, a classe de problemas solucionáveis em tempo exponencial por uma máquina de Turing não-determinísticas. Mais precisamente, EXPTIME ≠ NEXPTIME se e somente se existem sparse languages no NP que não são em P. EXPTIME também pode ser reformulado como o APSPACE classe de espaço, os problemas que podem ser resolvidos por uma alternating Turing machine no espaço polinomial. Esta é uma maneira de ver que EXPTIME PSPACE, já que uma máquina de Turing alternada é pelo menos tão poderoso quanto uma máquina de Turing determinista. EXPTIME é uma classe em uma hierarquia de classes de complexidade exponencial, com limites de tempo cada vez mais elevados. A classe 2-EXPTIME é definida de forma semelhante ao EXPTIME mas com um tempo vinculado duplamente exponencial. Isto pode ser generalizado para limites de tempo cada vez mais altos. (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的方式，因為已知交替式圖靈機至少跟確定型圖靈機計算能力一樣。 EXPTIME是指數譜系（exponential hierarchy）內的其中一個複雜度類。2-EXPTIME這個複雜度類則使用類似EXPTIME的定義方式，但是使用（Double exponential function）的時間限制。使用類似方式可以類推出更高的時間上限。 (zh)
- Експоненціальний алгоритм, EXPTIME (від англ. Exponential Time — експоненційний час) — в теорії складності обчислень, клас задач, які розв'язні на машині Тюринга за час O(2p(n))), де p(n) — поліноміальна функція від n. (uk)
|
| 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)
|
