| dbo:abstract
|
- In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in (asymptotically) more space, subject to certain conditions. For example, a deterministic Turing machine can solve more decision problems in space n log n than in space n. The somewhat weaker analogous theorems for time are the time hierarchy theorems. The foundation for the hierarchy theorems lies in the intuition thatwith either more time or more space comes the ability to compute morefunctions (or decide more languages). The hierarchy theorems are usedto demonstrate that the time and space complexity classes form ahierarchy where classes with tighter bounds contain fewer languagesthan those with more relaxed bounds. Here we define and prove thespace hierarchy theorem. The space hierarchy theorems rely on the concept of space-constructible functions. The deterministic and nondeterministic space hierarchy theorems state that for all space-constructible functions f(n), , where SPACE stands for either DSPACE or NSPACE, and o refers to the little o notation. (en)
- Na teoria da complexidade computacional, o teorema de hierarquia de espaço é resultado da separação que mostra que tanto as máquinas determinísticas quanto as não-determinísticas podem resolver mais problemas em mais espaço (assintoticamente), sob certas condições. Por exemplo, uma máquina de Turing determinística pode resolver mais problema de decisão em espaço n log n do que em espaço n. O teorema análogo para o tempo é o teorema de hierarquia de tempo. A base para os teoremas de hierarquia reside na intuição de que com mais espaço ou com mais tempo vem a capacidade de computar mais funções (ou decidir mais linguagens). Os teoremas de hierarquia são utilizados para demonstrar que as classes de complexidade de tempo e de espaço, formam uma hierarquia onde classes com limitantes menores contém menos linguagens do que aquelas com limitantes maiores. Aqui vamos definir e provar o teorema de hierarquia do espaço. Este teorema depende do conceito de função espaço construtível. O teorema de hierarquia do espaço determinístico e não-determinístico assumem que para todas as funções espaço construtível f(n), que , onde SPACE pode ser tanto DSPACE quanto NSPACE. (pt)
- 在计算复杂性理论中，空间阶层定理（英語：Space hierarchy theorem）是一组结论，它们表明在一定条件下，确定型和不确定型图灵机在可用的（渐进）存储空间越多时，能用于解答的问题也就越多。例如，一个确定型图灵机在使用存储空间时可以求解比使用存储空间时更多的决定性问题。在时间复杂度分析中的类似结论是时间阶层定理。 阶层定理的提出建立在这样的直觉之上：能允许使用的时间或空间越多，就应该能求解更多函数（或决定更多语言）。阶层定理可以用来展现时间或空间复杂度类可以形成一个金字塔型结构：约束越紧，则能决定的语言就越少。 (zh)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 14278 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- 在计算复杂性理论中，空间阶层定理（英語：Space hierarchy theorem）是一组结论，它们表明在一定条件下，确定型和不确定型图灵机在可用的（渐进）存储空间越多时，能用于解答的问题也就越多。例如，一个确定型图灵机在使用存储空间时可以求解比使用存储空间时更多的决定性问题。在时间复杂度分析中的类似结论是时间阶层定理。 阶层定理的提出建立在这样的直觉之上：能允许使用的时间或空间越多，就应该能求解更多函数（或决定更多语言）。阶层定理可以用来展现时间或空间复杂度类可以形成一个金字塔型结构：约束越紧，则能决定的语言就越少。 (zh)
- In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in (asymptotically) more space, subject to certain conditions. For example, a deterministic Turing machine can solve more decision problems in space n log n than in space n. The somewhat weaker analogous theorems for time are the time hierarchy theorems. , where SPACE stands for either DSPACE or NSPACE, and o refers to the little o notation. (en)
- Na teoria da complexidade computacional, o teorema de hierarquia de espaço é resultado da separação que mostra que tanto as máquinas determinísticas quanto as não-determinísticas podem resolver mais problemas em mais espaço (assintoticamente), sob certas condições. Por exemplo, uma máquina de Turing determinística pode resolver mais problema de decisão em espaço n log n do que em espaço n. O teorema análogo para o tempo é o teorema de hierarquia de tempo. , onde SPACE pode ser tanto DSPACE quanto NSPACE. (pt)
|
| rdfs:label
|
- Teorema de hierarquia de espaço (pt)
- Space hierarchy theorem (en)
- 空间阶层定理 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
