# ZŁO

## Zadanko o w#w na zwykłej MT

**Zadanie**
Mamy do dyspozycji jednotaśmową maszynę Turinga. Chcemy pokazać, że do rozpoznania $L = \{w\#w: w \in \{0, 1\}^* \}$ potrzeba $\Omega(n^2)$ czasu.

**Rozwiązanie**

Niech $M$ będzie MT rozpoznającą $L$.

Rozważmy rodzinę języków $L_n = \{w0^n\#w0^n : w \in \{0, 1\}^*, |w|=n\}$. Oczywiście dla każdego $n$ mamy wtedy $L_n \subset L$.

Będziemy śledzić działanie $M$ dla $x \in L_n$. Ponumerujmy zera w lewej połówce $x$ od $1$ do $n$. Dla $i$-tego zera rozważmy kolejne momenty, gdy głowica przechodzi pomiędzy nim oraz jego prawym sąsiadem (zerem nr $i + 1$ lub haszem). Możemy wypisać obok siebie kolejne stany, które ma wtedy maszyna. Otrzymamy w ten sposób pewien ciąg stanów. Taki ciąg dla słowa $x$ oraz $i$-tego zera oznaczymy przez $S_i(x)$. Zbiór wszystkich takich ciągów dla danego słowa $x$ oznaczymy przez $S(x) = \{S_i(x) : 1 \leq i \leq n \}$

Kluczowy lemat: dla $x \neq y$ $(x, y \in L_n)$ zachodzi $S(x) \cap S(y) = \emptyset$

Dowód: gdyby było inaczej, to bso. dla pewnych $i \leq j$ mamy $S_i(x) = S_j(y)$. Weźmy prefiks słowa $x$ kończący się $i$-tym zerem oraz sufiks $y$ zaczynający się $j$-tym zerem. Następnie sklejmy je tak, że pierwsze/ostatnie zero się połączą. Oczywiście $M$ akceptuje $x$ oraz $y$. Z definicji $S_i$ sklejone słowo również zostanie zaakceptowane. Nie należy jednak ono do $L$, co daje sprzeczność.

Mając udowodniony lemat będziemy chcieli pokazać, że dla pewnego słowa $x$ najkrótszy ciąg w $S(x)$ ma długość $\Omega(n)$. Każdy ze zbiorów $S$ zawiera $\Omega(n)$ ciągów. To oznacza, że dla słowa $x$ ich sumaryczna długość będzie równa $\Omega(n^2)$. To daje nam już tezę zadania: odpowiada to identycznej złożoności maszyny, gdyż każdy element danego ciągu odpowiada jednemu ruchowi (i każdemu ruchowi odpowiada co najwyżej jeden element w jednym ciągu).

Ciągów o długości $\leq d$ jest $\sum_{i \leq d} c^d = \frac{1 - c^d}{1 - c}$, gdzie $c = |Q|$. Skoro zbiory $S$ mają parami puste przekroje, to muszą w szczególności zawierać parami różne najkrótsze ciągi. Zbiorów takich jest $2^n$ (tyle ile słów w $L_n$). Niech $D =$ max$_x$ min$_i$ $C_i(x)$. Z zasady szufladkowej mamy więc $\frac{1 - c^D}{1 - c} \geq 2^n$. Z tego bezpośrednio wynika, że $D = \Omega(n)$, co kończy dowód.

## Pewna* technika z lematem translacyjnym

Ogólny problem: robimy dowód nie wprost i chcemy, używając lematu, dla założenia że $G(\text{coś ciut większego}) \subseteq G(\text{coś małego})$ dojść do założenia $G(\text{coś sporo większego}) \subseteq G(\text{coś małego})$, które da nam wystarczającą różnicę wielkości, żeby dojść do sprzeczności używając twierdzeń o hierarchii.

Przeszkoda jest taka, że często pojedyncze użycie lematu za mało pompuje nam cosie. Można więc spróbować użyć lematu kilka razy i skonstruować taki ciąg:

$G(\text{coś}_k) \subseteq G(\text{coś}_{k - 1}) \subseteq ... \subseteq G(\text{coś}_1)$

gdzie coś$_k$ to nasze "coś sporo większego", kolejne cosie z malejącymi indeksami są coraz mniejsze, aż w końcu coś$_1$ to nasze "coś małego"

Kluczowe pytanie to jak wymyślić pośrednie cosie.

### Dowód że $NSPACE(n^3) \subset NSPACE(n^4)$, który pokazuje to na przykładzie

Zacznijmy od przykładu, gdzie chcemy pokazać, że $NSPACE(n^3) \subset NSPACE(n^4)$. Nieostre zawieranie jest oczywiste, chcemy więc tylko pokazać że nie może być równości, czyli że nie może zajść $NSPACE(n^4) \subseteq NSPACE(n^3)$.

To standardowo załóżmy nie wprost, że tak jest:
$NSPACE(n^4) \subseteq NSPACE(n^3)$

Lemat translacyjny dla $f_1(n) = 2^n$ da nam:
$NSPACE(2^{4n}) \subseteq NSPACE(2^{3n})$

To teraz szukamy takiej $f_2(n)$, żeby dla oryginalnego zawierania po prawej (tam gdzie $n^3$) wyszło to co tu wyszło po lewej (czyli $2^{4n}$). Będzie tak dla $f_2(n) = 2^{\frac{4}{3}n}$, używając lematu na oryginalnym zawieraniu oraz $f_2$ dostajemy:
$NSPACE(2^{\frac{16}{3}n}) \subseteq NSPACE(2^{4n})$

Możemy tak zrobić jeszcze raz, tym razem chcąc z $n^3$ zrobić $2^{\frac{16}{3}n}$, co realizuje $f_3(n) = 2^{\frac{16}{9}n}$. Mamy więc takie zawierania:

$NSPACE(2^{4n}) \subseteq NSPACE(2^{3n})$
$NSPACE(2^{\frac{16}{3}n}) \subseteq NSPACE(2^{4n})$
$NSPACE(2^{\frac{64}{9}n}) \subseteq NSPACE(2^{\frac{16}{3}n})$

Możemy je teraz zapisać obok siebie i połączyć identyczne prawe strony z lewymi - to będą nasze cosie:

$NSPACE(2^{\frac{64}{9}n}) \subseteq NSPACE(2^{\frac{16}{3}n}) \subseteq NSPACE(2^{4n}) \subseteq NSPACE(2^{3n})$

czyli w szczególności $NSPACE(2^{\frac{64}{9}n}) \subseteq NSPACE(2^{3n})$, i dalej już wiadomo co zrobić:

$DSPACE(2^{\frac{64}{9}n}) \subseteq NSPACE(2^{\frac{64}{9}n}) \subseteq NSPACE(2^{3n}) \subseteq_{(Savitch)} DSPACE(2^{6n})$

czyli w szczególności $DSPACE(2^{\frac{64}{9}n}) \subseteq DSPACE(2^{6n})$, co przeczy tw. o hierarchii pamięciowej, bo $inf_{n \rightarrow \infty} \frac{2^{6n}}{2^{\frac{64}{9}n}} = inf_{n \rightarrow \infty} 2^{-\frac{10}{9}n} = 0$, więc z tw. mamy $DSPACE(2^{\frac{64}{9}n}) \supset DSPACE(2^{6n})$

### Ogólny dowód że $NSPACE(n^r) \subset NSPACE(n^{r + \epsilon})$ dla $r \geq 0, \epsilon > 0$

Teza już jest zapisana powyżej, intuicję daje przykład z $n^3$ oraz $n^4$, zatem zapiszę tu tylko dowód.

Wstępna uwaga: zakładamy $r > 0$, przypadek z $r = 0$ trzeba rozważyć osobno i już nam się nie chciało, pewnie wystarczy wskazać przykład czegoś co się da zrobić w $n^{\epsilon}$, a nie da się w stałej pamięci i uważać na niedeterminizm (może jakiś język bezkontekstowy, który np da się rozpoznać w $log^k$?).

Ustalmy $r, \epsilon > 0$. Tak jak wcześniej musimy tylko pokazać, że nie zachodzi $NSPACE(n^{r + \epsilon}) \subseteq NSPACE(n^r)$. Załóżmy nie wprost że tak jest.

Użyjemy teraz $k + 1$ razy lematu (wartość $k$ dobierzemy za chwilę). W kolejnych krokach będziemy chceli użyć lematu z takimi funkcjami $f_i(n)$, żeby zachodziło $(f_i(n))^r = (f_{i - 1}(n))^{r + \epsilon}$, co pozwoli nam "skleić" ze sobą lewe i prawe strony odpowiednich zawierań, tak jak w powyższym przykładzie. Jeśli zapomnimy na chwilę o $n$, wyobrażając sobie że $f_i$ to liczby spełniające powyższą zależność, oraz oznaczymy $a_i = log(f_i)$, to chcemy $(r + \epsilon) a_{i - 1} = r a_i$, więc możemy wziąć $a_i = (\frac{r + \epsilon}{r})^i$. Łatwo dostrzec, że wobec tego za $f_i(n)$ wystarczy wziąć $2^{na_i}$.

Używając $k + 1$ razy lematu dostaniemy:

$NSPACE(2^{n a_k (r + \epsilon)}) \subseteq ... \subseteq NSPACE(2^{n a_0 r}) = NSPACE(2^{n r})$

Zauważmy, że $a_i$ rosną wykładniczo, zatem istnieje $k$ (i nawet jest stosunkowo małe), takie że $a_k(r + \epsilon) > 3r$. Weźmy więc takie $k$, wtedy:

$NSPACE(2^{3nr}) \subseteq NSPACE(2^{n a_k (r + \epsilon)}) \subseteq NSPACE(2^{n r})$

i dalej już klasycznie Savitch + sprzeczność z hierarchią pamięci:

$DSPACE(2^{3nr}) \subseteq NSPACE(2^{3nr}) \subseteq NSPACE(2^{n r}) \subseteq DSPACE(2^{2nr})$

ale $inf_{n \rightarrow \infty} \frac{2^{2nr}}{2^{3nr}} = 0$, więc z tw. o hierarchii pamięci $DSPACE(2^{2nr}) \subset DSPACE(2^{3nr})$

---

*niektórzy uważają, że tu jest literówka i powinno być "piwna"