In computational complexity theory, non-deterministic space or NSPACE is the computational resource describing the memory space for a non-deterministic Turing machine. It is the non-deterministic counterpart of DSPACE.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - NSPACE (ca)
- NSPACE (de)
- NSPACE (es)
- NSPACE (fr)
- NSPACE (ja)
- NSPACE (en)
- NSPACE (pt)
- NSPACE (zh)
|
| rdfs:comment
| - En teoría de la complejidad computacional, la clase de complejidad NSPACE(f(n)) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no determinista en espacio O(f(n)) y tiempo ilimitado. NSPACE es la contrapartida no determinista de DSPACE. La clase de complejidad NPSPACE se puede definir a partir de NSPACE como:
* Datos: Q1756295 (es)
- In computational complexity theory, non-deterministic space or NSPACE is the computational resource describing the memory space for a non-deterministic Turing machine. It is the non-deterministic counterpart of DSPACE. (en)
- En théorie de la complexité, NSPACE désigne une famille de classes de complexité caractérisées par leur complexité en espace sur une machine de Turing non déterministe. Plus précisément, est la classe des problèmes de décision qui, pour une entrée de taille , peuvent être décidés par une machine de Turing non déterministe fonctionnant en espace . (fr)
- 計算複雑性理論において、複雑性クラス NSPACE(f(n)) とは、非決定性チューリング機械で領域 O(f(n)) と無制限の時間で解ける決定問題の集合である。DSPACEの非決定性バージョンである。 複雑性クラス NPSPACE は NSPACE を使って以下のように定義できる。 (ja)
- 在計算複雜度理論內，NSPACE(f(n))這個複雜度類是一個決定性問題的集合，裡面的問題可以以非確定型圖靈機使用O(f(n))這麼多空間，不限制時間來解決。或者，換句話說，這是的非確定型版本。 有一些重要的複雜度類可以使用NSPACE來定義。這些複雜度類包括了：
* REG = DSPACE(O(1)) = NSPACE(O(1))，這裡 REG是正則語言(regular language)的複雜度類(非確定的特性在常數空間之內並沒有增加計算的能力)。
* NL = NSPACE(O(log n))
* CSL = NSPACE(O(n))，這裡CSL是上下文有關語言(context-sensitive language)的複雜度類。
* PSPACE = NPSPACE =
* EXPSPACE = NEXPSPACE = 最後兩個結論是從薩維奇定理導出，這定理指出對任何f(n) ≥ log(n)， NSPACE(f(n)) ⊆ DSPACE(f2(n))。 則指出對任何s(n) ≥ log n，NSPACE(s(n))在補集運算下封閉(closed under complement)。 NSPACE可以與DTIME作連接如下：對任何 s(n), (zh)
- En teoria de la complexitat, la classe de complexitat NSPACE(f(n)) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing no determinista en espai O(f(n)) i temps il·limitat. Es la contrapartida no determinista de la classe DSPACE. Diverses classe de complexitat es defineixen en funció de DSPACE:
* REG = DSPACE(O(1)) = NSPACE(O(1)).
* NL = NSPACE(O(log n))
* CSL = NSPACE(O(n)), on CSL és la classe dels llenguatges sensibles al context
* PSPACE = NPSPACE =
* EXPSPACE = NEXPSPACE = (ca)
- NSPACE (selten auch NTAPE, von englisch: Non-deterministic Turing machine tape) ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der theoretischen Informatik. Dort steht NSPACE(f) für die Platzkomplexitätsklasse der Entscheidungsprobleme, die von einer Nichtdeterministischen Turingmaschine mit Platzbedarf O(f) gelöst werden können. Es ist das nichtdeterministische Gegenstück zu DSPACE. NSPACE(f(n)) ist gegen Komplement abgeschlossen (Satz von Immerman und Szelepcsényi). (de)
- Em teoria da complexidade computational, a classe de complexidade NSPACE(f(n)) é um conjunto de problemas de decisão que podem ser resolvido por uma máquina de Turing não-determinística usando espaço O(f(n)), e tempo ilimitado. É o equivalente não-determinístico da DSPACE. Diversas classes de complexidade podem ser definidas em termos do NSPACE. Tais como: Os últimos dois resultados abaixo derivam do teorema de Savitch, este define que para qualquer função f(n) ≥ log(n), NSPACE(f(n)) ⊆ DSPACE(f2(n)). NSPACE pode ser relacionada a DTIME tal como abaixo para qualquer s(n), (pt)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - En teoria de la complexitat, la classe de complexitat NSPACE(f(n)) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing no determinista en espai O(f(n)) i temps il·limitat. Es la contrapartida no determinista de la classe DSPACE. Diverses classe de complexitat es defineixen en funció de DSPACE:
* REG = DSPACE(O(1)) = NSPACE(O(1)).
* NL = NSPACE(O(log n))
* CSL = NSPACE(O(n)), on CSL és la classe dels llenguatges sensibles al context
* PSPACE = NPSPACE =
* EXPSPACE = NEXPSPACE = Una generalització d'aquesta classe és , que es defineix amb màquines de Turing alternants. (ca)
- NSPACE (selten auch NTAPE, von englisch: Non-deterministic Turing machine tape) ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der theoretischen Informatik. Dort steht NSPACE(f) für die Platzkomplexitätsklasse der Entscheidungsprobleme, die von einer Nichtdeterministischen Turingmaschine mit Platzbedarf O(f) gelöst werden können. Es ist das nichtdeterministische Gegenstück zu DSPACE. NSPACE(f(n)) ist gegen Komplement abgeschlossen (Satz von Immerman und Szelepcsényi). Mit NSPACE werden häufig andere Komplexitätsklassen definiert. So kann NPSPACE wie folgt aus NSPACE hergeleitet werden: (de)
- En teoría de la complejidad computacional, la clase de complejidad NSPACE(f(n)) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no determinista en espacio O(f(n)) y tiempo ilimitado. NSPACE es la contrapartida no determinista de DSPACE. La clase de complejidad NPSPACE se puede definir a partir de NSPACE como:
* Datos: Q1756295 (es)
- In computational complexity theory, non-deterministic space or NSPACE is the computational resource describing the memory space for a non-deterministic Turing machine. It is the non-deterministic counterpart of DSPACE. (en)
- En théorie de la complexité, NSPACE désigne une famille de classes de complexité caractérisées par leur complexité en espace sur une machine de Turing non déterministe. Plus précisément, est la classe des problèmes de décision qui, pour une entrée de taille , peuvent être décidés par une machine de Turing non déterministe fonctionnant en espace . (fr)
- 計算複雑性理論において、複雑性クラス NSPACE(f(n)) とは、非決定性チューリング機械で領域 O(f(n)) と無制限の時間で解ける決定問題の集合である。DSPACEの非決定性バージョンである。 複雑性クラス NPSPACE は NSPACE を使って以下のように定義できる。 (ja)
- Em teoria da complexidade computational, a classe de complexidade NSPACE(f(n)) é um conjunto de problemas de decisão que podem ser resolvido por uma máquina de Turing não-determinística usando espaço O(f(n)), e tempo ilimitado. É o equivalente não-determinístico da DSPACE. Diversas classes de complexidade podem ser definidas em termos do NSPACE. Tais como:
* REG = DSPACE(O(1)) = NSPACE(O(1)), onde REG é a classe da linguagens regulares (não-determinismo não adiciona poder a um espaço constante).
* NL = NSPACE(O(log n))
* CSL = NSPACE(O(n)), onde CSL é a classe das linguagens sensíveis ao contexto.
* PSPACE = NPSPACE =
* EXPSPACE = NEXPSPACE = Os últimos dois resultados abaixo derivam do teorema de Savitch, este define que para qualquer função f(n) ≥ log(n), NSPACE(f(n)) ⊆ DSPACE(f2(n)). O Teorema de Immerman–Szelepcsényi diz que NSPACE(s(n)) é fechada sob a complementação para qualquer função s(n) ≥ log n. NSPACE pode ser relacionada a DTIME tal como abaixo para qualquer s(n), (pt)
- 在計算複雜度理論內，NSPACE(f(n))這個複雜度類是一個決定性問題的集合，裡面的問題可以以非確定型圖靈機使用O(f(n))這麼多空間，不限制時間來解決。或者，換句話說，這是的非確定型版本。 有一些重要的複雜度類可以使用NSPACE來定義。這些複雜度類包括了：
* REG = DSPACE(O(1)) = NSPACE(O(1))，這裡 REG是正則語言(regular language)的複雜度類(非確定的特性在常數空間之內並沒有增加計算的能力)。
* NL = NSPACE(O(log n))
* CSL = NSPACE(O(n))，這裡CSL是上下文有關語言(context-sensitive language)的複雜度類。
* PSPACE = NPSPACE =
* EXPSPACE = NEXPSPACE = 最後兩個結論是從薩維奇定理導出，這定理指出對任何f(n) ≥ log(n)， NSPACE(f(n)) ⊆ DSPACE(f2(n))。 則指出對任何s(n) ≥ log n，NSPACE(s(n))在補集運算下封閉(closed under complement)。 NSPACE可以與DTIME作連接如下：對任何 s(n), (zh)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[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)