About: Space hierarchy theorem

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Space hierarchy theorem Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : el.dbpedia.org associated with source document(s)

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.

Attributes	Values
rdfs:label	Space hierarchy theorem (en)
rdfs: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. 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)
sameAs	Space hierarchy theorem Space hierarchy theorem
dbp:wikiPageUsesTemplate	dbt:Cite_book dbt:Cleanup dbt:Mvar dbt:Reflist dbt:Short_description dbt:Tmath dbt:Sans-serif
Subject	Articles containing proofs Structural complexity theory Theorems in computational complexity theory
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Space_hierarchy_theorem?oldid=1035987802&ns=0
Wikipage page ID	663050 (xsd:integer)
page length (characters) of wiki page	14401 (xsd:nonNegativeInteger)
Wikipage revision ID	1035987802 (xsd:integer)
has 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)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Space_hierarchy_theorem
is Wikipage redirect of	Space hierarchy
is Link from a Wikipage to another Wikipage of	List of theorems NP-completeness Turing machine List of mathematical logic topics Complexity class Algorithmic complexity Constructible function Counter-machine model Counter machine EXPTIME List of computability and complexity topics Gap theorem

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (71 GB total memory, 995 MB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software