[Teoria złożoności] twierdzenie Savitcha
- niebieska_biedronka
- Użytkownik
- Posty: 397
- Rejestracja: 8 paź 2011, o 15:31
- Płeć: Kobieta
- Lokalizacja: Kraków
- Podziękował: 96 razy
- Pomógł: 19 razy
[Teoria złożoności] twierdzenie Savitcha
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....
Ostatnio zmieniony 15 sty 2015, o 12:39 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
- niebieska_biedronka
- Użytkownik
- Posty: 397
- Rejestracja: 8 paź 2011, o 15:31
- Płeć: Kobieta
- Lokalizacja: Kraków
- Podziękował: 96 razy
- Pomógł: 19 razy
[Teoria złożoności] twierdzenie Savitcha
\(\displaystyle{ \textnormal{NSPACE}(f(n))\subseteq\textnormal{DSPACE}(f^2(n))}\)
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
[Teoria złożoności] twierdzenie Savitcha
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.
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
- Użytkownik
- Posty: 397
- Rejestracja: 8 paź 2011, o 15:31
- Płeć: Kobieta
- Lokalizacja: Kraków
- Podziękował: 96 razy
- Pomógł: 19 razy
[Teoria złożoności] twierdzenie Savitcha
Rozumiem, że graf jest skierowany?
Skoro szukanie ścieżki w grafie odpowiada przejściom automatu niedeterministycznego, to skąd ten deterministyczny się tam bierze?
Skoro szukanie ścieżki w grafie odpowiada przejściom automatu niedeterministycznego, to skąd ten deterministyczny się tam bierze?
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
[Teoria złożoności] twierdzenie Savitcha
Graf skierowany. Deterministyczny masz zbudować, taki który będzie dowodził, że \(\displaystyle{ L\in DSPACE(f(n)^2)}\)
- niebieska_biedronka
- Użytkownik
- Posty: 397
- Rejestracja: 8 paź 2011, o 15:31
- Płeć: Kobieta
- Lokalizacja: Kraków
- Podziękował: 96 razy
- Pomógł: 19 razy
[Teoria złożoności] twierdzenie Savitcha
OK. Muszę jeszcze dokładnie się w to wczytać, w razie czego pozwolę sobie zadać jeszcze jakieś pytanko dziękuję!