JFiZO - Lista 10
JFIZO - Zadanie 09.085
Jeśli A \in NP, to istnieje NTM M_A.
Maszyna niedeterministyczna podczas obliczenia korzysta z niedeterminizmu wtedy, gdy ma więcej niż jedną możliwą akcję, dla jednej konfiguracji.
Możemy zmodyfikować maszynę, aby najpierw wyznaczała sobie na taśmie pewien obszar, zapisała na nim tyle liczb, ile ma niedeterministycznych wyborów w obliczeniu. Potem przechodzimy do normalnego obliczenia. W momencie natrafienia na niejednoznaczną konfigurację, czytamy pierwszą z wylosowanych liczb od lewej, niech to będzie i, kasujemy ją i wybieramy i-tą regułę deterministycznie.
Zlozonosc M_A niech bedzie p krokow. Wtedy musimy zapisac max p komorek po |Q| (ilosc stanow) * 2 (lewo lub prawo) * ilosc_charow (bo moge zamienic to co mam na tasmie na cos innego)$ - 
tak?
JFiZO - Zadanie 86
Jeśli A \subseteq N^2 należy do P, to istnieje maszyna Turinga M_A i wielomian p takie, że M_A rozpoznaje czy n \in A po nie więcej niż p(|n|) krokach.
Rozważmy zbiór \Pi=\{n:\exists m. |m|\leq p(|n|) \wedge (n,m)\in A \}.
Skonstruujmy niedeterministyczną maszynę Turinga M_{\Pi}, która najpierw wyznacza blok o długości p(|n|) (za obecną zawartością taśmy), niedeterministycznie zapisuje go zerami i jedynkami, a potem zachowuje się jak M_A, gdzie niedeterministycznie zgadnięta liczba to m.
M_{\Pi} rozpoznaje \Pi, więc \Pi jest w NP.
- M_{\Pi} =
- read n
- guess m
- run M_a(n,m)
- accept if M_a accepts, reject otherwise
JFiZO - Zadanie 87
Z tresci zadania:
- B \in NP
- p - wielomian
- A \subset N^2, A \in P
- B = \{n: \exists m: |m| \le p(|n|), (n,m) \in A\}
Miejmy:
- M_B - niedeterministyczna machina turinga rozstrzyga przynaleznosc do tego zbioru.
M_B determinuje przynaleznosc n do zbioru B zgadujac ciag stanow przez ktore przechodzi. Stanow w tym ciagu jest conajwyzej p(|n|) (z definicji przynaleznosci do NP). Ten ciag stanow mozemy zakodowac jako ciag liczb naturalnych. Ten ciag liczb naturalnych mozemy zakodowac jako liczba naturalna. Niech ta liczba to m. Jesli wiec (n,m) \in A. Znamy wiec sekwencje stanow przez ktora musimy przejsc, mozemy wiec w wielomianowym czasie rozstrzygnac zbior A.
Stanow niech bedzie s. Elementow w ciagu stanow e. Niech na kazdym kroku podejmujemy decyzje ktory z s stanow niedeterministycznie wybrac. Wtedy mamy max s*e wyborow. Jest to wielomianowa liczba wyborow. p = s*e.
JFIZO - Zadanie 09.090
- H <_P H_d. Po prostu dla każdej nieskierowanej krawędzi \{v_1, v_2\} z grafu H, do grafu H_d dodajemy dwie skierowane krawędzie <v_1, v_2> i <v_2, v_1>.
- H_d <_P H. Dla każdego wierzchołka v z H_d, do H dodajemy wierzchołki v, v_{in} i v_{out}.
Dla każdej skierowanej krawędzi <w, v> z H_d dodajemy do H nieskierowane krawędzie \{w_{out}, v_{in}\}.
- Oprócz tego dla każdego wierzchołka v z H_d dodajemy do H krawędzie \{v_{in}, v\} oraz \{v, v_{out}\}.
Dlaczego jeden wierzchołek reprezentujemy trzema, a nie dwoma? Bo inaczej nie moglibyśmy pamiętać pętelek <v, v>.
