https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=NTIME 2026-05-27T21:40:47Z Versionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale Kopie MediaWiki 1.43.8 https://wiki-de.moshellshocker.dns64.de/index.php?title=NTIME&diff=269277&oldid=prev 2023-07-29T13:08:57Z

<p>Parameterfehler gefixt</p> <p><b>Neue Seite</b></p><div>In der [[Komplexitätstheorie]] steht &#039;&#039;&#039;NTIME&#039;&#039;&#039;(&#039;&#039;f&#039;&#039;) für die Menge der Sprachen, die von einer [[nichtdeterministische Turingmaschine|nichtdeterministischen Turingmaschine]] in Zeit &#039;&#039;O&#039;&#039;(&#039;&#039;f&#039;&#039;) [[Akzeptieren (Automaten- und Komplexitätstheorie)|akzeptiert]] werden können.<br /> <br /> Mittels &#039;&#039;&#039;NTIME&#039;&#039;&#039; werden unter anderem folgende Komplexitätsklassen definiert bzw. charakterisiert:<br /> * [[Q (Komplexitätsklasse)|&#039;&#039;&#039;Q&#039;&#039;&#039;]]=&#039;&#039;&#039;NTIME&#039;&#039;&#039;(&#039;&#039;n&#039;&#039;) (Formal wird [[Q (Komplexitätsklasse)|&#039;&#039;&#039;Q&#039;&#039;&#039;]] als Familie aller Sprachen &#039;&#039;&#039;L&#039;&#039;&#039; mit &#039;&#039;&#039;L=L(M)&#039;&#039;&#039; definiert, wobei jede Berechnung von &#039;&#039;&#039;M&#039;&#039;&#039; auf Eingabe &#039;&#039;&#039;w&#039;&#039;&#039; höchstens &#039;&#039;&#039;|w|&#039;&#039;&#039; Schritte benötigt&lt;ref&gt;{{cite conference |conference=1st Annual ACM Symposium on Theory of Computing | title = Quasi-realtime languages (Extended Abstract) | language=en | last = Book | first = Ronald V. | last2 = Greibach | first2 = Sheila A. | date = 1969 | publisher = ACM | book-title = Proceedings of the 1st Annual ACM Symposium on Theory of Computing, May 5-7, 1969, Marina del Rey, CA, USA | pages = 15–18 | doi = 10.1145/800169.805416}}&lt;/ref&gt;. In vorheriger Quelle wird auch gezeigt, dass diese Klasse mit &#039;&#039;&#039;NTIME(n)&#039;&#039;&#039; zusammenfällt.)<br /> * [[NP (Komplexitätsklasse)|&#039;&#039;&#039;NP&#039;&#039;&#039;]]:=&lt;math&gt;\bigcup_{k=0}^\infty&lt;/math&gt; &#039;&#039;&#039;NTIME&#039;&#039;&#039;(&#039;&#039;n&#039;&#039;&lt;sup&gt;&#039;&#039;k&#039;&#039;&lt;/sup&gt;)<br /> * &#039;&#039;&#039;NE&#039;&#039;&#039;:=&#039;&#039;&#039;NTIME&#039;&#039;&#039;(2&lt;sup&gt;&#039;&#039;O&#039;&#039;(&#039;&#039;n&#039;&#039;)&lt;/sup&gt;)<br /> * [[NEXPTIME|&#039;&#039;&#039;NEXP&#039;&#039;&#039;]]:=&lt;math&gt;\bigcup_{k=0}^\infty&lt;/math&gt; &#039;&#039;&#039;NTIME&#039;&#039;&#039;(2&lt;sup&gt;&#039;&#039;n&#039;&#039;&lt;sup&gt;&#039;&#039;k&#039;&#039;&lt;/sup&gt;&lt;/sup&gt;)<br /> <br /> Mittels [[Cantor-Diagonalisierung|Diagonalisierung]] lässt sich zeigen, dass die Teilmengenbeziehung in der Hierarchie [[Q (Komplexitätsklasse)|&#039;&#039;&#039;Q&#039;&#039;&#039;]] &amp;sub; [[NP (Komplexitätsklasse)|&#039;&#039;&#039;NP&#039;&#039;&#039;]] &amp;sub; &#039;&#039;&#039;NE&#039;&#039;&#039; &amp;sub; [[NEXPTIME |&#039;&#039;&#039;NEXP&#039;&#039;&#039;]] [[echte Teilmenge|echt]] sind.<br /> <br /> == Weblinks ==<br /> * {{Complexity Zoo|NTIME|N#ntime}}<br /> <br /> == Einzelnachweise ==<br /> &lt;references /&gt;<br /> <br /> [[Kategorie:Komplexitätsklasse]]<br /> [[Kategorie:Abkürzung]]</div>

imported>Wiki1939