This HTML5 document contains 84 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n15http://portal.acm.org/
n21https://global.dbpedia.org/id/
n20http://www.cs.berkeley.edu/~luca/cs172-04/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-pthttp://pt.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-zhhttp://zh.dbpedia.org/resource/
n22https://archive.org/details/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

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