NTIME (f) podzbiór DSPACE (f)

Jak stwierdza pytanie, w jaki sposób udowodnimy, że ? $\textbf{NTIME}(f(n)) \subseteq \textbf{DSPACE}(f(n))$

Czy ktoś może wskazać mi dowód lub nakreślić go tutaj? Dzięki!

complexity-theory time-complexity space-complexity gdiazc
źródło

Myślę, że jest ich wiele. stałe chowające się tam. Możesz udowodnić, że . Wystarczy wymienić wszystkie możliwe niedeterministyczne domysły algorytmu i uruchomić algorytm z tymi domysłami. Zaakceptuj, jeśli jedna z domysłów prowadzi do stanu akceptacji.

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,

Dlaczego nie uczynić tego odpowiedzią?

Yuval Filmus,

@IgorShinkar Istnieją różne wyniki, takie jak twierdzenie o liniowym przyspieszeniu i twierdzenie o kompresji taśmy, które mówią, że można pozbyć się tych stałych w „większości” okoliczności. liniowe mówi, że dla dowolnego ; kompresja taśmy mówi, że , znowu dla każdego .

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

Odpowiedzi:

Oto rozszerzona wersja komentarza Igora Shinkara. Najprostszym sposobem na symulację niedeterministycznej maszyny działającej w czasie i przestrzeni użycie przestrzeni . Wymieniamy wszystkie możliwe rzuty monetami, symulując oryginalną maszynę na każdym z nich; wymaga to miejsca do przechowywania rzutów monet oraz miejsca do symulacji rzeczywistej maszyny. Istnieje tutaj niewielka trudność: kiedy rzuty monetą są „odczytywane” przez (oryginalną) maszynę, musimy jakoś zaznaczyć, gdzie jesteśmy w sekwencji rzutów monet; możemy użyć dodatkowego bitu na rzut monetą. Prawdopodobnie można to jeszcze bardziej zoptymalizować. $f(n)$ $s(n) \leq f(n)$ $s(n) + 2f(n) + O(1)$ $f(n)$ $s(n)$

Jeśli będziemy ostrożni, możemy być w stanie uzyskać coś jeszcze lepszego, ponieważ w każdym uruchomieniu programu łączna liczba rzutów monetą i całkowita użyta przestrzeń sumują się co najwyżej . Podejrzewam, że można uruchomić symulację w przestrzeni . Być może będziemy musieli do tego założyć coś takiego jak . $f(n)$ $(1+o(1))f(n)$ $f(n) = \Omega(\log n)$

Jak wspomina Igor, zwykle klasy ograniczone do zasobów są definiowane tylko „do dużego O”, tak że wynik, który używa spacji , wciąż znajduje się w . $O(f(n))$ $\mathrm{DSPACE}(f(n))$

Yuval Filmus
źródło