| rdfs:comment
| - In der Komplexitätstheorie steht EXPSPACE (Exponential Space) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer deterministischen Turingmaschine in durch Platz entschieden werden können,wobei ein beliebiges Polynom ist. Betrachtet man nicht-deterministische Turingmaschinen, so erhält man die Klasse NEXPSPACE.Nach dem Satz von Savitch gilt EXPSPACE = NEXPSPACE. In der DSPACE / NSPACE-Notation ausgedrückt gilt also: (de)
- En théorie de la complexité, EXPSPACE est la classe des problèmes décidables en espace exponentiel par une machine de Turing déterministe. (fr)
- En teoria de la complexitat, la classe de complexita EXPSPACE és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en espai O(2p(n)), on p(n) és una funció polinomial sobre n. D'acord amb el teorema de Savitch, aquesta classe és igual a la que considera màquines de Turing no deterministes. Quan es restringeix p(n) a una funció lineal, la classe resultant s'anomena . En termes de DSPACE es té EXPSPACE conté de manera estricta les classes PSPACE, NP-Complet, NP i P i es creu que també conté estrictament el conjunt EXPTIME. (ca)
- In computational complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i.e., in space, where is a polynomial function of . Some authors restrict to be a linear function, but most authors instead call the resulting class ESPACE. If we use a nondeterministic machine instead, we get the class NEXPSPACE, which is equal to EXPSPACE by Savitch's theorem. EXPSPACE is a strict superset of PSPACE, NP, and P and is believed to be a strict superset of EXPTIME. (en)
- En teoría de la complejidad computacional, la clase de complejidad EXPSPACE es el conjunto de los problemas de decisión que pueden ser resueltos con una máquina de Turing determinista en espacio O(2p(n)), donde p(n) es una función polinomial sobre n. De acuerdo con el Teorema de Savitch, esta clase es igual a la que considera máquinas de Turing no deterministas. Cuando se restringe p(n) como una función lineal, la clase resultante se denomina ESPACE. En términos de DSPACE, (es)
- 計算複雑性理論において、複雑性クラス EXPSPACE とは、決定性チューリング機械で O(2p(n)) の領域を使って解ける全決定問題の集合である。ここで、p(n) は n の多項式関数である。p(n) を一次関数に限定する場合もあるが、通常そのようなクラスは ESPACE と呼ばれる。 DSPACEの記法では以下のように表される。 EXPSPACE完全な決定問題とは、EXPSPACE に属し、かつ全ての EXPSPACE に属する問題を多項式時間多対一還元によってその問題に帰着させることができる場合を指す。換言すれば、多項式時間アルゴリズムによって、ある問題から別の問題へ解を変えずに変換可能である。EXPSPACE完全問題は、EXPSPACEの中でも最も難しい問題とされる。 EXPSPACE は PSPACE、NP、P を真に包含する。また、EXPTIME をも真に包含すると考えられている。 EXPSPACE完全な問題の例として、2つの正規表現が異なる言語を表現しているかどうかの決定問題がある。このとき、その表現は4つの演算子（和集合、連結、クリーネ閉包（ゼロ個以上のコピー）、平方（2つのコピー））に制限される。 クリーネ閉包を除くと、この問題は NEXPTIME完全となる。これは EXPTIME完全に似ているが、決定性ではなく非決定性チューリング機械で定義される。 (ja)
- Nella teoria della complessità, EXPSPACE è l'insieme di tutti i risolvibili da una macchina deterministica di Turing nello spazio O(2p(n)), dove p(n) è una funzione polinomiale di n. (Alcuni autori restringono p(n) all'essere una funzione lineare, ma la maggior parte degli autori invece chiamano la classe risultante .) Se usiamo invece una macchina non deterministica, otteniamo la classe NEXPSPACE, che è uguale a EXPSPACE per il teorema di Savitch. In termini di e , EXPSPACE è un superinsieme stretto di PSPACE, NP e P e si crede sia un superinsieme stretto di EXPTIME. (it)
- 계산 복잡도 이론에서 EXPSPACE는 결정론적 튜링 기계가 공간을 써서 풀 수 있는 판정 문제의 집합이다. 여기서 은 에 대한 다항함수이다. (일부에서는 을 선형 함수로 제한하기도 하지만, 대부분은 그러한 경우를 로 정의한다.) 에 대한 식으로 정리하면 아래와 같다. 어떤 판정 문제가 EXPSPACE이고, EXPSPACE에 있는 모든 문제가 그 문제로 될 수 있으면, EXPSPACE-완전이라고 한다. 다시 말해서, 한 인스턴스를 다른 똑같은 해의 인스턴스로 변환하는 다항 시간 알고리즘이 존재한다는 뜻이다. EXPSPACE-완전 문제는 EXPSPACE 문제 가운데 가장 어려운 문제들일 것으로 추정되고 있다. PSPACE, , 는 모두 EXPSPACE의 진부분집합이다. EXPTIME 역시 EXPSPACE의 진부분집합이라는 설이 유력하다. EXPSPACE-complete의 예로는 두 정규 표현식이 다른 언어를 나타내는지 알아내는 문제가 있다. 여기서 표현식은 합집합, , 클레이니 스타 (0회 이상 반복), 제곱 (표현식 2회 반복) 네 연산자로 제한한다. (ko)
- Em teoria da complexidade computacionais, EXPSPACE é o conjunto de todos os problemas de decisão solúveis por uma máquina de Turing determinística em espaço O(2p(n)) onde p(n) é uma função polinomial de n. (Alguns autores restringem p(n) para uma função linear, mas a maioria chama a classe resultante de ESPACE.) Se, por outro lado, nós usamos uma máquina não determinísitica, teremos a classe NEXPSPACE, que é igual a EXPSPACE pelo teorema de savitch. Em termos de DSPACE e NSPACE, temos que EXPSPACE é um conjunto que engloba PSPACE, NP, and P e acredita-se que também englobe EXPTIME. (pt)
- 在計算複雜度理論內，EXPSPACE是一個包含可以在O(2p(n))空間內解決的決定性問題的集合，這裡的p(n)是某個n的多項式。（有些作者認為p(n）應該限制為線性函數，但是多數的人把這這樣的複雜度類稱作ESPACE。)如果我們使用非決定性圖靈機，我們會得到複雜度類NEXPSPACE。根據薩維奇定理，這個複雜度類等同EXPSPACE。 以和NSPACE表示： 我們說一個問題是EXPSPACE-完全，如果這問題本身在EXPSPACE內，而且存在多項式多對一歸約，令所有在EXPSPACE內的題目都可以歸約成這個題目。換句話說，存在一個多項式時間的演算法可以將一個狀況換成其他題目的另一個狀況，並且答案一樣。EXPSPACE-完全的題目也可以想做是EXPSPACE裡面最難的題目。 EXPSPACE是PSPACE，NP，和P的嚴格母集（前者包含且不等於後者）。並且也被相信是EXPTIME的嚴格母集。 一個EXPSPACE-完全的例子是分辨兩個正規表式是否是一樣的語言這個問題。這裡的表示限制使用四種操作子：聯集，，克萊尼星號（可以是零個或多個重複的表示式），和平方（兩份表示式）。 如果我們排除星號，則這個問題變成NEXPTIME-完全，這個複雜度類有點類似EXPTIME-完全，不過使用的機器是非決定性圖靈機而非一般的圖靈機。 (zh)
|
| has abstract
| - En teoria de la complexitat, la classe de complexita EXPSPACE és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en espai O(2p(n)), on p(n) és una funció polinomial sobre n. D'acord amb el teorema de Savitch, aquesta classe és igual a la que considera màquines de Turing no deterministes. Quan es restringeix p(n) a una funció lineal, la classe resultant s'anomena . En termes de DSPACE es té La classe de complexitat és la classe de problemes que estan a EXPSPACE tals que tot problema d'EXPSPACE tenen una transformació polinòmica cap a cada un dels problemes d'EXPSPACE-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 EXPSPACE-complet pot esser vist com el conjunt de problemes més difícils d'EXPSPACE. EXPSPACE conté de manera estricta les classes PSPACE, NP-Complet, NP i P i es creu que també conté estrictament el conjunt EXPTIME. El 1980, va demostrar que el problema de verificar o falsar qualsevol expressió de primer ordre sobre els nombres reals que només utilitza suma i comparació però no multiplicació està a EXPSPACE. (ca)
- In der Komplexitätstheorie steht EXPSPACE (Exponential Space) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer deterministischen Turingmaschine in durch Platz entschieden werden können,wobei ein beliebiges Polynom ist. Betrachtet man nicht-deterministische Turingmaschinen, so erhält man die Klasse NEXPSPACE.Nach dem Satz von Savitch gilt EXPSPACE = NEXPSPACE. In der DSPACE / NSPACE-Notation ausgedrückt gilt also: (de)
- In computational complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i.e., in space, where is a polynomial function of . Some authors restrict to be a linear function, but most authors instead call the resulting class ESPACE. If we use a nondeterministic machine instead, we get the class NEXPSPACE, which is equal to EXPSPACE by Savitch's theorem. A decision problem is EXPSPACE-complete if it is in EXPSPACE, and every problem in EXPSPACE has a polynomial-time many-one reduction to it. In other words, there is a polynomial-time algorithm that transforms instances of one to instances of the other with the same answer. EXPSPACE-complete problems might be thought of as the hardest problems in EXPSPACE. EXPSPACE is a strict superset of PSPACE, NP, and P and is believed to be a strict superset of EXPTIME. (en)
- En teoría de la complejidad computacional, la clase de complejidad EXPSPACE es el conjunto de los problemas de decisión que pueden ser resueltos con una máquina de Turing determinista en espacio O(2p(n)), donde p(n) es una función polinomial sobre n. De acuerdo con el Teorema de Savitch, esta clase es igual a la que considera máquinas de Turing no deterministas. Cuando se restringe p(n) como una función lineal, la clase resultante se denomina ESPACE. En términos de DSPACE, La clase de complejidad EXPSPACE-completo es la clase de los problemas que están en EXPSPACE tales que todo problema de EXPSPACE tiene una transformación polinomial hacia cada uno de los problemas de EXPSPACE-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 EXPSPACE-completo puede ser visto como el conjunto de los problemas más difíciles de EXPSPACE. EXPSPACE contiene de forma estricta las clases PSPACE, NP-completo, NP y P y se cree que también contiene estrictamente el conjunto EXPTIME. Un ejemplo de problema en EXPSPACE-completo es el de decidir si dos expresiones regulares representan lenguajes diferentes, cuando los operadores regulares utilizados son la unión, la concatenación, la clausura de Kleene (cero o más copias de una expresión), y el cuadrado (dos copias de una expresión). Si no se incluye la clausura de Kleene, el problema es NEXPTIME-completo, que es como EXPTIME-completo, salvo que se define según las máquinas de Turing no-deterministas. En 1980, L. Berman demostró que el problema de verificar o falsificar cualquier expresión de primer orden sobre los números reales que solo utiliza suma y comparación (pero no multiplicación) está en EXPSPACE. (es)
- En théorie de la complexité, EXPSPACE est la classe des problèmes décidables en espace exponentiel par une machine de Turing déterministe. (fr)
- 計算複雑性理論において、複雑性クラス EXPSPACE とは、決定性チューリング機械で O(2p(n)) の領域を使って解ける全決定問題の集合である。ここで、p(n) は n の多項式関数である。p(n) を一次関数に限定する場合もあるが、通常そのようなクラスは ESPACE と呼ばれる。 DSPACEの記法では以下のように表される。 EXPSPACE完全な決定問題とは、EXPSPACE に属し、かつ全ての EXPSPACE に属する問題を多項式時間多対一還元によってその問題に帰着させることができる場合を指す。換言すれば、多項式時間アルゴリズムによって、ある問題から別の問題へ解を変えずに変換可能である。EXPSPACE完全問題は、EXPSPACEの中でも最も難しい問題とされる。 EXPSPACE は PSPACE、NP、P を真に包含する。また、EXPTIME をも真に包含すると考えられている。 EXPSPACE完全な問題の例として、2つの正規表現が異なる言語を表現しているかどうかの決定問題がある。このとき、その表現は4つの演算子（和集合、連結、クリーネ閉包（ゼロ個以上のコピー）、平方（2つのコピー））に制限される。 クリーネ閉包を除くと、この問題は NEXPTIME完全となる。これは EXPTIME完全に似ているが、決定性ではなく非決定性チューリング機械で定義される。 また1980年、L. Berman は実数の加法と比較（乗法は含まない）についての一階述語論理式の評価問題が EXPSPACE であることを示した。 (ja)
- 계산 복잡도 이론에서 EXPSPACE는 결정론적 튜링 기계가 공간을 써서 풀 수 있는 판정 문제의 집합이다. 여기서 은 에 대한 다항함수이다. (일부에서는 을 선형 함수로 제한하기도 하지만, 대부분은 그러한 경우를 로 정의한다.) 에 대한 식으로 정리하면 아래와 같다. 어떤 판정 문제가 EXPSPACE이고, EXPSPACE에 있는 모든 문제가 그 문제로 될 수 있으면, EXPSPACE-완전이라고 한다. 다시 말해서, 한 인스턴스를 다른 똑같은 해의 인스턴스로 변환하는 다항 시간 알고리즘이 존재한다는 뜻이다. EXPSPACE-완전 문제는 EXPSPACE 문제 가운데 가장 어려운 문제들일 것으로 추정되고 있다. PSPACE, , 는 모두 EXPSPACE의 진부분집합이다. EXPTIME 역시 EXPSPACE의 진부분집합이라는 설이 유력하다. EXPSPACE-complete의 예로는 두 정규 표현식이 다른 언어를 나타내는지 알아내는 문제가 있다. 여기서 표현식은 합집합, , 클레이니 스타 (0회 이상 반복), 제곱 (표현식 2회 반복) 네 연산자로 제한한다. 클레이니 스타가 없다면 이 문제는 -완전 문제가 된다. -완전은 비결정론적 튜링 기계로 정의한다는 점을 빼면 EXPTIME-완전과 비슷하다. 베르만은 1980년에 덧셈과 비교만 포함하는 실수 일차 논리식을 검증하는 문제가 EXPSPACE라는 것을 보였다. (이 논리식은 곱셈을 포함하지 않는다) (ko)
- Nella teoria della complessità, EXPSPACE è l'insieme di tutti i risolvibili da una macchina deterministica di Turing nello spazio O(2p(n)), dove p(n) è una funzione polinomiale di n. (Alcuni autori restringono p(n) all'essere una funzione lineare, ma la maggior parte degli autori invece chiamano la classe risultante .) Se usiamo invece una macchina non deterministica, otteniamo la classe NEXPSPACE, che è uguale a EXPSPACE per il teorema di Savitch. In termini di e , Un problema di decisione è EXPSPACE-completo se è in EXPSPACE, e ogni problema in EXPSPACE ha una ad esso. In altre parole, c'è un algoritmo di tempo polinomiale che trasforma richieste dell'uno in richieste dell'altro con la stessa risposta. I problemi EXPSPACE-completi potrebbero essere pensati come i problemi più difficili in EXPSPACE. EXPSPACE è un superinsieme stretto di PSPACE, NP e P e si crede sia un superinsieme stretto di EXPTIME. Un esempio di un problema EXPSPACE-completo è quello di riconoscere se due espressioni regolari rappresentano linguaggi diversi, dove le espressioni sono limitate a quattro operatori: unione, concatenazione, la stella di Kleene (zero o più copie di un'espressione) e quadratura (due copie di un'espressione). Se si tralascia la stella di Kleene, allora quel problema diventa -completo, che è come EXPTIME-completo, tranne che è definito in termini di macchine di Turing non deterministiche anziché deterministiche. È stato anche mostrato da L. Berman nel 1980 che il problema di verificare/falsificare una qualsiasi affermazione del primo ordine sui numeri reali che implichi soltanto l'addizione e il confronto (ma non la moltiplicazione) è in EXPSPACE. (it)
- Em teoria da complexidade computacionais, EXPSPACE é o conjunto de todos os problemas de decisão solúveis por uma máquina de Turing determinística em espaço O(2p(n)) onde p(n) é uma função polinomial de n. (Alguns autores restringem p(n) para uma função linear, mas a maioria chama a classe resultante de ESPACE.) Se, por outro lado, nós usamos uma máquina não determinísitica, teremos a classe NEXPSPACE, que é igual a EXPSPACE pelo teorema de savitch. Em termos de DSPACE e NSPACE, temos que Um problema de decisão é EXPSPACE-completo se este está em EXPSPACE, e para todo problema em EXPSPACE existe uma reduçao polinomial para este dado problema. Em outras palavras, existe um algoritmo polinomial que transforma as instâncias de um para as instâncias da outra com as mesmas respostas. EXPSPACE-completo podem ser vistos como os problemas mais difícieis do universo de problemas em EXPSPACE. EXPSPACE é um conjunto que engloba PSPACE, NP, and P e acredita-se que também englobe EXPTIME. Um exemplo de problema EXPSPACE-completo é o problema de reconhecer se duas expressões regulares reperesentam linguagens diferentes, quando a expressão é limitada para quatro operadores: União, Concatenação, Estrela, ou Quadrado. Se Estrela não for considerada, então o problema se torna NEXPTIME-completo, que é tal como EXPTIME-complete, exceto pelo fato de ser definido em termos de uma máquina de Turing não determinística em vez de uma determinística. Também foi mostrado por L. Berman em 1980 que o problema de verificar/falsificar qualquer clausula da lógica de primeira ordem sobre números reais que envolva adição ou comparação (mas não multiplicação) também está em EXPSPACE. (pt)
- 在計算複雜度理論內，EXPSPACE是一個包含可以在O(2p(n))空間內解決的決定性問題的集合，這裡的p(n)是某個n的多項式。（有些作者認為p(n）應該限制為線性函數，但是多數的人把這這樣的複雜度類稱作ESPACE。)如果我們使用非決定性圖靈機，我們會得到複雜度類NEXPSPACE。根據薩維奇定理，這個複雜度類等同EXPSPACE。 以和NSPACE表示： 我們說一個問題是EXPSPACE-完全，如果這問題本身在EXPSPACE內，而且存在多項式多對一歸約，令所有在EXPSPACE內的題目都可以歸約成這個題目。換句話說，存在一個多項式時間的演算法可以將一個狀況換成其他題目的另一個狀況，並且答案一樣。EXPSPACE-完全的題目也可以想做是EXPSPACE裡面最難的題目。 EXPSPACE是PSPACE，NP，和P的嚴格母集（前者包含且不等於後者）。並且也被相信是EXPTIME的嚴格母集。 一個EXPSPACE-完全的例子是分辨兩個正規表式是否是一樣的語言這個問題。這裡的表示限制使用四種操作子：聯集，，克萊尼星號（可以是零個或多個重複的表示式），和平方（兩份表示式）。 如果我們排除星號，則這個問題變成NEXPTIME-完全，這個複雜度類有點類似EXPTIME-完全，不過使用的機器是非決定性圖靈機而非一般的圖靈機。 L. Berman在1980年證明了，證明或反證任何有關實數並且牽涉加法和比較大小（但不牽涉乘法）的一階陳述，這個問題在EXPSPACE內。 (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)