Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Space_hierarchy_theorem> ?p ?o. }
Showing items 1 to 26 of
26
with 100 items per page.
- Space_hierarchy_theorem 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.".
- Space_hierarchy_theorem wikiPageExternalLink citation.cfm?id=763728.
- Space_hierarchy_theorem wikiPageExternalLink noteh.pdf.
- Space_hierarchy_theorem wikiPageID "663050".
- Space_hierarchy_theorem wikiPageRevisionID "603203151".
- Space_hierarchy_theorem hasPhotoCollection Space_hierarchy_theorem.
- Space_hierarchy_theorem subject Category:Articles_containing_proofs.
- Space_hierarchy_theorem subject Category:Structural_complexity_theory.
- Space_hierarchy_theorem subject Category:Theorems_in_computational_complexity_theory.
- Space_hierarchy_theorem type Abstraction100002137.
- Space_hierarchy_theorem type Communication100033020.
- Space_hierarchy_theorem type Message106598915.
- Space_hierarchy_theorem type Proposition106750804.
- Space_hierarchy_theorem type Statement106722453.
- Space_hierarchy_theorem type Theorem106752293.
- Space_hierarchy_theorem type TheoremsInDiscreteMathematics.
- Space_hierarchy_theorem comment "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.".
- Space_hierarchy_theorem label "Space hierarchy theorem".
- Space_hierarchy_theorem label "Teorema de hierarquia de espaço".
- Space_hierarchy_theorem sameAs Teorema_de_hierarquia_de_espaço.
- Space_hierarchy_theorem sameAs m.030thv.
- Space_hierarchy_theorem sameAs Q7572588.
- Space_hierarchy_theorem sameAs Q7572588.
- Space_hierarchy_theorem sameAs Space_hierarchy_theorem.
- Space_hierarchy_theorem wasDerivedFrom Space_hierarchy_theorem?oldid=603203151.
- Space_hierarchy_theorem isPrimaryTopicOf Space_hierarchy_theorem.