NTIME (f) Teilmenge von DSPACE (f)

Wie beweisen wir, wie in der Frage angegeben, dass ? $\textbf{NTIME}(f(n)) \subseteq \textbf{DSPACE}(f(n))$

Kann mich hier jemand auf einen Beweis hinweisen oder umreißen? Vielen Dank!

complexity-theory time-complexity space-complexity gdiazc
quelle

Ich denke es gibt mult. dort versteckte Konstanten. Sie können beweisen, dass . Zählen Sie einfach alle möglichen nicht deterministischen Vermutungen des Algorithmus auf und führen Sie Ihren Algorithmus mit diesen Vermutungen aus. Akzeptieren Sie, wenn eine der Vermutungen zu einem akzeptierenden Zustand führt.

N T I M E (f (n)) \subseteq D S P A C E (2 \cdot f (n))

$NTIME(f(n)) \subseteq DSPACE(2\cdot f(n))$

Igor Shinkar

Warum nicht eine Antwort geben?

Yuval Filmus

@IgorShinkar Es gibt verschiedene Ergebnisse, wie den Satz der linearen Beschleunigung und den Satz der Bandkomprimierung, die besagen, dass Sie diese Konstanten unter "den meisten" Umständen entfernen können. Die lineare Beschleunigung besagt, dass für jedes ; Die Bandkomprimierung besagt, dass erneut für jedes .

D T I M E (f (n)) \subseteq D T I M E (ϵ f (n) + n + 2)

$\mathrm{DTIME}(f(n)) \subseteq \mathrm{DTIME}(\epsilon f(n)+n+2)$

ϵ > 0

$\epsilon>0$

D S P A C E (f (n)) \subseteq D S P A C E (ϵ f (n) + O (1))

$\mathrm{DSPACE}(f(n))\subseteq \mathrm{DSPACE}(\epsilon f(n) + O(1))$

ϵ > 0

$\epsilon>0$

David Richerby

Antworten:

Hier ist eine erweiterte Version von Igor Shinkars Kommentar. Der einfachste Weg, eine nicht deterministische Maschine zu simulieren, die in der Zeit und im Raum läuft, verwendet Raum. Wir zählen alle möglichen Münzwürfe auf und simulieren die Originalmaschine auf jedem von ihnen. Dies erfordert Platz zum Speichern der Münzwürfe und Platz zum Simulieren der tatsächlichen Maschine. Hier gibt es eine leichte Schwierigkeit: Wenn die Münzwürfe von der (Original-) Maschine "gelesen" werden, müssen wir irgendwie markieren, wo wir uns in der Reihenfolge der Münzwürfe befinden; Wir können ein zusätzliches Bit pro Münzwurf verwenden. Es ist wahrscheinlich möglich, dies noch weiter zu optimieren. $f(n)$ $s(n) \leq f(n)$ $s(n) + 2f(n) + O(1)$ $f(n)$ $s(n)$

Wenn wir vorsichtig sind, können wir möglicherweise etwas noch Besseres erzielen, da in jedem Programmlauf die Gesamtzahl der Münzwürfe und der insgesamt verwendete Platz höchstens . Ich vermute, dass es möglich ist, die Simulation im Raum auszuführen . Vielleicht müssen wir dafür so etwas wie annehmen . $f(n)$ $(1+o(1))f(n)$ $f(n) = \Omega(\log n)$

Wie Igor erwähnt, werden normalerweise ressourcengebundene Klassen nur "bis zu großem O" definiert, sodass sich das Ergebnis, das den Raum , immer noch in . $O(f(n))$ $\mathrm{DSPACE}(f(n))$

Yuval Filmus
quelle