[Teoria złożoności] twierdzenie Savitcha

niebieska_biedronka · Post autor: **niebieska_biedronka** » 15 sty 2015, o 10:02

Potrzebuję w miarę jasny dowód tw. Savitcha jeśli ktoś takowym dysponuję, to będę niezmiernie wdzięczna. Znalazłam oczywiście w internecie jeden, który wykorzystuje rozwiązanie problemu REACHABILITY - i o ile chyba jestem w stanie przyswoić sobie algorytm rozwiązujący ten problem w czasie \(\displaystyle{ \mathcal{O}(f(n)^2)}\), o tyle nie rozumiem, jaki to ma związek z wyjściowym twierdzeniem....

Zordon · Post autor: **Zordon** » 15 sty 2015, o 10:30

W jakiej wersji potrzebujesz to twierdzenie?

niebieska_biedronka · Post autor: **niebieska_biedronka** » 15 sty 2015, o 11:07

\(\displaystyle{ \textnormal{NSPACE}(f(n))\subseteq\textnormal{DSPACE}(f^2(n))}\)

Zordon · Post autor: **Zordon** » 15 sty 2015, o 13:33

No więc akceptowanie inputu \(\displaystyle{ x}\) w NSPACE jest równoważne znalezieniu ścieżki od konfiguracji startowej do konfiguracji końcowej w grafie konfiguracji.
Konfiguracja to:
- taśma długości f(n)
- stan
- położenie głowicy.

Krawędzie odpowiadają poprawnym przejściom automatu niedeterministycznego.
Można szukać ścieżki w tym grafie zużywając \(\displaystyle{ O(f(n)^2)}\) pamięci. Dowód jak dla REACHABILITY.

niebieska_biedronka · Post autor: **niebieska_biedronka** » 15 sty 2015, o 19:48

Rozumiem, że graf jest skierowany?

Skoro szukanie ścieżki w grafie odpowiada przejściom automatu niedeterministycznego, to skąd ten deterministyczny się tam bierze?

Zordon · Post autor: **Zordon** » 15 sty 2015, o 23:37

Graf skierowany. Deterministyczny masz zbudować, taki który będzie dowodził, że \(\displaystyle{ L\in DSPACE(f(n)^2)}\)

niebieska_biedronka · Post autor: **niebieska_biedronka** » 16 sty 2015, o 22:55

OK. Muszę jeszcze dokładnie się w to wczytać, w razie czego pozwolę sobie zadać jeszcze jakieś pytanko dziękuję!