Hierarchie czasu w DSPACE (O (s)))

Twierdzenie o hierarchii czasu stwierdza, że maszyny Turinga mogą rozwiązać więcej problemów, jeśli mają (wystarczająco) więcej czasu. Czy to w jakiś sposób się utrzymuje, jeśli przestrzeń jest asymptotycznie ograniczona? Jak $\textrm{DTISP}(g(n), O(s(n)))$ odnosi się do $\textrm{DTISP}(f(n), O(s(n)))$ jeśli $\frac{f}{g}$ rośnie wystarczająco szybko?

Ja szczególnie zainteresowany w przypadku, $s(n) = n$ , $g(n) = n^3$ i $f(n) = 2^n$ .

W szczególności uważa się języka: $L_k := \{ (\langle M \rangle, w) \; : \; \text{M rejects } (\langle M \rangle, w) \text{ using at most } |\langle M \rangle, w|^3 \text{ time steps},$ $k * |\langle M \rangle, w| \text{ cells and four different tape symbols} \}$

Jednakże, $L_k$ może zostać podjęta decyzja, $n^3$ etapach stosując $(k+1)n \in O(n)$ przestrzeni.

Bez ograniczania $M$ do czterech symboli taśmy, a tym samym pozwalając na kompresję komórek $O(n)$ do $n$ komórek, mamy problemy z przestrzenią podczas symulacji $M$ ze zbyt dużą liczbą symboli taśmy. W takim przypadku języka nie ma już w $\text{DSPACE}(O(n))$ . To samo dzieje się, gdy ustawia się $k = h(|w|)$ na pewien $h$ który można obliczyć wystarczająco szybko.

To pytanie jest w zasadzie przeformułowaniem mojego pytania tutaj .

Edycja Podsumowanie: zmieniono $\textrm{DSPACE}(s(n)) \cap \textrm{DTIME}(f(n))$ do $\textrm{DTISP}(f(n), s(n))$ , jednak, to, że przecięcie Warto także pomyśleć.

cc.complexity-theory complexity-classes turing-machines space-bounded time-hierarchy Henning
źródło

\frac{f}{g}

$\frac{f}{g}$

\cap

$\cap$

Ups ... Właściwie napisałem najpierw D-SPACE (O (s))) - CZAS (g (n)), ale nie podobało mi się to, co zrobiło z niego MathJax, więc szybko to zmieniłem do DSPACE (O (s (n))) ∩ DTIME (g (n)) bez większego zastanowienia. Moje początkowe pytanie dotyczy tego, co napisałem jako pierwsze, ale przecięcie DSPACE (O (s (n))) ∩ DTIME (g (n)) jest również bardzo interesujące - cieszę się, że popełniłem ten błąd. Wyraźnie DTISP (g (n), s (n)) ⊆ DTIME (g (n)) ∩ DSPACE (s)). Czy to właściwe włączenie? Według Wikipedii, jej właściwość nie jest znana dla DTISP (P, PolyL) ⊆ DTIME (P) ∩ DSPACE (PolyL): wikiwand.com/en/SC_(kompleksowość)

Henning

Chłodny!! Dziękuję Ci za wyjaśnienie. Naprawdę interesują mnie tego rodzaju problemy. :)

Michael Wehar

D T I S P (2^{n}, n) = D S P A C E (n)

$DTISP(2^n,n)=DSPACE(n)$

k

$k$

k

$k$

k

$k$

Odpowiedzi:

$\mathrm{DTISP}(O(n \log n),O(n)) = \mathrm{DSPACE}(O(n))$ $\mathrm{NSPACE}(O(n))$ $\mathrm{DTIME}(O(n))⊆\mathrm{DSPACE}(O(n/\log n))$

Jednak w prawdopodobnych przypuszczeniach o złożoności obliczeniowej istnieje odpowiednia hierarchia. Na przykład, jeśli dla każdego , CIRCUIT-SAT ∉ io- , to gdzie , wynosi , a jest konstruowalne w czasoprzestrzeni. $ε>0$ $O(2^{n-ε})$ $\mathrm{DTISP}(O(f),O(s(n))) ⊊ \mathrm{DTISP}(O(f^{1+ε}),O(s(n)))$
$f(n)≥n$ $f(n)$ $2^{o(\min(n,s(n)))}$ $f$

W szczególności (zgodnie z hipotezą) istnienie zadowalającego przypisania dla obwodów z i rozmiarem służy jako kontrprzykład na równość klas. $⌊\mathrm{lg}(f^{1+ε/2})⌋$ $(\log f)^{O(1)}$

Uwagi:

CIRCUIT-SAT jest co najmniej tak samo twardy jak -SAT (który jest stosowany w silnej hipotezie wykładniczej czasu). $k$
Zgodnie z konwencją, w CIRCUIT-SAT, oznacza liczbę przewodów wejściowych; rozmiar obwodu wynosi . $n$ $n^{O(1)}$
Jeśli w założeniu zastosowano CIRCUIT-SAT dla rozmiarów obwodu quasilinowego, wówczas ograniczenie na można rozluźnić do . Również słabsze / silniejsze założenia dotyczące twardości CIRCUIT-SAT dają słabsze / silniejsze hierarchie (które możemy obecnie udowodnić). $f(n)$ $O((2-ε)^{\min(n,s(n))})$
IO oznacza nieskończenie często i może być porzucone dla które są w pewnym sensie ciągłe (w tym ). $f$ $f(n)=n^a$
Wydaje się prawdopodobne, że hierarchia DTISP jest wystarczająco ostra, aby odróżnić od (i być może ) (gdy nie jest zbyt duże w stosunku do dozwolonej przestrzeni). $O(f)$ $o(f/\log f)$ $o(f)$ $f$
Aby odróżnić od , potrzebujemy tylko słabszego założenia P ≠ PSPACE. $n^a$ $2^n$

Dmytro Taranovsky
źródło