Czy DSPACE (n) = DSPACE (1,5n)?

Z twierdzenia o hierarchii przestrzeni wiadomo, że jeśli $f$ można konstruować w przestrzeni, to DSPACE ( $2f(n)$ ) nie jest równe DSPACE ( $f(n))$ .

Tutaj przez DSPACE ( $f(n))$ mam na myśli klasę wszystkich problemów, które można rozwiązać w przestrzeni $f(n)$ za pomocą maszyny Turinga z ustalonym alfabetem. Pozwala to rozpatrywać twierdzenie o hierarchii kosmicznej z taką dokładnością.

Standardowy argument podaje stałą multiplikatywną $2$ : potrzebujemy przestrzeni $f(n)$ do skonstruowania obliczenia jakiejś maszyny Turinga za pomocą maszyny uniwersalnej. Potrzebujemy również $f(n)$ aby rozwiązać problem z zatrzymaniem.

Pytanie: Czy DSPACE ( $f(n)$ ) jest równe DSPACE ( $\frac{3}{2}f(n)$ )?

cc.complexity-theory complexity-classes Aleksiej Milovanov
źródło

Z jakiegokolwiek powodu jesteś zainteresowany

\frac{3}{2}

$\frac32$ ? Czy

1 + Ω (1)

$1+\Omega(1)$ byłby równie interesujący?

Thomas

Jak myślisz, dlaczego twierdzenie o hierarchii przestrzeni daje

? Przypuszczam, że argumentujesz, że potrzebujemy

miejsca na symulację i

miejsce do zliczania liczby kroków w celu uniknięcia nieskończonych pętli. Ale w obu przypadkach musimy najpierw zaznaczyć

lokację na taśmie (można to zrobić od czasu

2 f (n)

$2f(n)$

f (n)

$f(n)$

\log_{| Σ |} | Σ |^{f (n)}

$\log_{|\Sigma|} |\Sigma|^{f(n)}$

f (n)

$f(n)$

f

$f$ jest możliwe do zbudowania w przestrzeni) i jak zrobiłbyś to znakowanie? Twój argument jest w porządku, jeśli zakładasz, że maszyny nie mogą pisać *, ale w przeciwnym razie potrzebne są dalsze komplikacje.

domotorp

@Thomas Właściwie chcę

1 + o (1)

$1 + o(1)$

Alexey Milovanov

Odpowiedzi:

Można udowodnić, że DSPACE $(f(\frac 32 n))\ne$ DSPACE $(f(n))$ jeśli $f$ rośnie co najmniej liniowo przy użyciu prostego wariantu standardowego argumentu wypełniającego. Dla języka $L$ , niech $L'=\{x0^{|x|/2}\mid x\in L\}$ .

Roszczenie. $L\in$ DSPACE $(f(n))$ wtedy i tylko wtedy, gdy $L'\in$ DSPACE $(f(\frac 23n))$ jeśli $f(n)\ge \frac 32n$ .

(Moja pierwsza odpowiedź zawierała kilka niepoprawnych stwierdzeń, dzięki Emilowi za zauważenie tego.)

Najpierw pokażę, jak wykorzystać roszczenie do udowodnienia hierarchii. Ponieważ $f$ rośnie co najmniej liniowo, mamy DSPACE $(2f(n))\subset$ DSPACE $(f(2n))$ . Wybierz język $L\in$ DSPACE $(f(2n))\setminus$ DSPACE $(f(n))$ . Za pomocą twierdzenia, $L'\in$ dSPACE $(f(\frac 43 n))=$ DSPACE $(f(n))$ , gdzie ostatnia równość wynika z pośredniego założenia. Ale potem $L\in$ DSPACE $(f(\frac 32 n))=$ DSPACE $(f(n))$ , gdzie ostatnia równość jest znowu przez pośrednie założenie, co daje sprzeczność.

Dowód roszczenia. Jeżeli $L'\in$ DSPACE $(f(\frac 23 n))$ $L\in$ $(f(n))$ $|x|/2$ $x$ $L'$ $f(n)\ge \frac 32 n$ $f$ $x$

$L'$ $L'=\{x10^{|x|/2}\mid x\in L\}$ $x10^{|x|/2}$ $f$ $x10^{|x|/2}$ $f$

domotorp
źródło

L \in D S P A C E (f (n))

$L\in\mathrm{DSPACE}(f(n))$

L^{'} \in D S P A C E (f (\frac{2}{3} n))

$L'\in\mathrm{DSPACE}(f(\frac23n))$

\frac{2}{3}

$\frac23$

L^{'} \in D S P A C E (f (\frac{2}{3} n))

$L'\in\mathrm{DSPACE}(f(\frac23n))$

L \in D S P A C E (f (n) + \frac{n}{2})

$L\in\mathrm{DSPACE}(f(n)+\frac n2)$

L \in D S P A C E (2 f (n))

$L\in\mathrm{DSPACE}(2f(n))$

L^{'} \in D S P A C E (\frac{4}{3} f (n) + \frac{n}{3}))

$L'\in\mathrm{DSPACE}(\frac43f(n)+\frac n3))$

@Emil Masz rację. Próbowałem to naprawić, czy to wygląda lepiej?

domotorp

L^{'} \in D S P A C E (f (\frac{2}{3} n)) ⟹ L \in D S P A C E (f (n))

$L'\in\mathrm{DSPACE}(f(\frac23n))\implies L\in\mathrm{DSPACE}(f(n))$

O (\log n)

$O(\log n)$

f

$f$

D S P A C E (f (n)) ⊊ D S P A C E ((1 + ϵ) f (n))

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

ϵ > 0

$\epsilon>0$

f (n) < n

$f(n)<n$