https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=NSPACE 2026-05-26T22:24:17Z Versionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale Kopie MediaWiki 1.43.8 https://wiki-de.moshellshocker.dns64.de/index.php?title=NSPACE&diff=391188&oldid=prev 2020-03-14T22:18:56Z

<p><a href="/index.php/Kategorie:Abk%C3%BCrzung" title="Kategorie:Abkürzung">Kategorie:Abkürzung</a></p> <p><b>Neue Seite</b></p><div>&#039;&#039;&#039;NSPACE&#039;&#039;&#039; (selten auch NTAPE, von englisch: Non-deterministic Turing machine tape) ist ein Begriff aus der [[Komplexitätstheorie]], einem Teilgebiet der [[Theoretische Informatik|theoretischen Informatik]].<br /> <br /> Dort steht NSPACE(f) für die Platz[[komplexitätsklasse]] der [[Entscheidbar|Entscheidungsprobleme]], die von einer [[Nichtdeterministische Turingmaschine|Nichtdeterministischen Turingmaschine]] mit Platzbedarf [[Landau-Notation|O]](f) gelöst werden können. Es ist das nichtdeterministische Gegenstück zu [[DSPACE]]. NSPACE(f(n)) ist gegen Komplement abgeschlossen ([[Satz von Immerman und Szelepcsényi]]).<br /> <br /> Mit NSPACE werden häufig andere Komplexitätsklassen definiert. So kann [[NPSPACE]] wie folgt aus NSPACE hergeleitet werden:<br /> <br /> :&lt;math&gt;\mbox{NPSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(n^k)&lt;/math&gt;<br /> <br /> == Weblinks ==<br /> * {{Complexity Zoo|NSPACE|N#nspace}}<br /> <br /> [[Kategorie:Komplexitätsklasse]]<br /> [[Kategorie:Abkürzung]]</div>

imported>KnightMove