Space hierarchy theorem (original) (raw)
在计算复杂性理论中，空间阶层定理（英語：Space hierarchy theorem）是一组结论，它们表明在一定条件下，确定型和不确定型图灵机在可用的（渐进）存储空间越多时，能用于解答的问题也就越多。例如，一个确定型图灵机在使用存储空间时可以求解比使用存储空间时更多的决定性问题。在时间复杂度分析中的类似结论是时间阶层定理。 阶层定理的提出建立在这样的直觉之上：能允许使用的时间或空间越多，就应该能求解更多函数（或决定更多语言）。阶层定理可以用来展现时间或空间复杂度类可以形成一个金字塔型结构：约束越紧，则能决定的语言就越少。
| Property | Value |
|---|---|
| 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 | http://www.cs.berkeley.edu/~luca/cs172-04/noteh.pdf http://portal.acm.org/citation.cfm%3Fid=763728 https://archive.org/details/introductiontoth00sips |
| dbo:wikiPageID | 663050 (xsd:integer) |
| dbo:wikiPageLength | 14278 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1119314445 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cambridge_University_Press dbr:Big_O_Notation dbr:Little_o dbr:DSPACE dbr:Viliam_Geffert dbr:Decision_problem dbr:Depth-first_search dbr:EXPSPACE dbc:Articles_containing_proofs dbr:Computable_function dbr:NL_(complexity) dbc:Structural_complexity_theory dbr:Luca_Trevisan dbc:Theorems_in_computational_complexity_theory dbr:Computational_complexity_theory dbr:PSPACE dbr:Space-constructible_function dbr:Immerman–Szelepcsényi_theorem dbr:NSPACE dbr:Unary_language dbr:Time_hierarchy_theorem dbr:Savitch's_theorem dbr:Deterministic_Turing_machine |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Mvar dbt:Reflist dbt:Short_description dbt:Tmath dbt:Sans-serif |
| dct:subject | dbc:Articles_containing_proofs dbc:Structural_complexity_theory dbc:Theorems_in_computational_complexity_theory |
| rdf:type | yago:WikicatTheoremsInComputationalComplexityTheory yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 |
| 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 | freebase:Space hierarchy theorem yago-res:Space hierarchy theorem wikidata:Space hierarchy theorem dbpedia-pt:Space hierarchy theorem dbpedia-zh:Space hierarchy theorem https://global.dbpedia.org/id/4vVak |
| prov:wasDerivedFrom | wikipedia-en:Space_hierarchy_theorem?oldid=1119314445&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Space_hierarchy_theorem |
| is dbo:wikiPageRedirects of | dbr:Space_hierarchy |
| is dbo:wikiPageWikiLink of | dbr:List_of_computability_and_complexity_topics dbr:NP_(complexity) dbr:DSPACE dbr:List_of_mathematical_logic_topics dbr:PSPACE-complete dbr:Counter-machine_model dbr:Oracle_machine dbr:Constructible_function dbr:Complexity_class dbr:Computational_complexity_theory dbr:Gap_theorem dbr:EXPTIME dbr:PSPACE dbr:Counter_machine dbr:List_of_theorems dbr:PolyL dbr:Time_hierarchy_theorem dbr:Structural_complexity_theory dbr:Space_complexity dbr:Space_hierarchy |
| is foaf:primaryTopic of | wikipedia-en:Space_hierarchy_theorem |