Co bylo na wykladzie ?

20 lutego 2008

Wprowadzenie: trudność obliczeniowa -- od rozumienia empirycznego do modelu matematycznego. Problemów trudnych obliczeniowo
nie trzeba sztucznie konstruować, spotyka się je dość powszechnie,  np.  rozkład liczby naturalnej na czynniki (faktoryzacja).

Postęp technologiczny przyśpiesza czas działania komputerów o stałą multyplikatywną. Prosty rachunek pokazuje, że to ma znaczenie przy szybkich algorytmach (największe przy liniowych, przy wykładniczych -- prawie wcale).

Podstawowy model: maszyna Turinga off line, tzn. taśma wejściowa jest read only i nie wlicza się do rozmiaru pamięci (który moze być mniejszy niż liniowy).  Konfiguracja maszyny obejmuje zawartość taśm roboczych i położenie wszystkich głowic. Złożoność pamieciowa maszyny jest ograniczona przez funkcję S(n), jeśli dla dowolnego wejścia rozmiaru n, maszyna odwiedza co najwyżej S(n) komórek na wszystkich taśmach roboczych. Złożoność czasowa maszyny jest ograniczona przez funkcję T(n), jeśli dla dowolnego wejścia rozmiaru n, maszyna wykonuje co najwyżej T(n) kroków. Złożoność pamieciową S(n) lub czasową T(n) rozpatrujemy zawsze z dokładnością do stałej multiplikatywnej, bo ewentualnie powiekszając alfabet roboczy możemy zawsze "skompresować"  c S(n) do S(n) (podobnie dla T).
Zauważmy, że rozmiar konfiguracji maszyny, której złożoność pamięciowa jest ograniczona przez S(n), jest ograniczony przez
S(n) + O(log n) .  Składnik O(log n) odpowiedzialny jest położenie głowicy na taśmie wejściowej.  Można go pominać, jeśli S(n) >= log (n)
--  na mocy uwagi o kompresowaniu o stałą.

Hipoteza P=/=NP będzie dokładniej omawiana później, ale "na rozgrzewkę" rozważymy następujący

Problem Levina: czy jest możliwe, że udowodnimy, że P=NP, ale nie będziemy znali algorytmu wielomianowego dla problemu SAT?
Otóż, używając numeracji maszyn Turinga można podać taki algorytm, że jeśli w ogóle istnieje algorytm wielomianowy dla SAT, to podany algorytm również działa w czasie wielomianowym, przynajmniej dla przypadków pozytywnych (tzn. gdy formuła jest spełnialna).
Dla konstrukcji istotne znaczenie ma fakt, że w przypadku problemu SAT z algorytmu odpowiadającego na pytanie czy istnieje rozwiazanie
(tzn. wartościowanie spełniające formułę), można otrzymać algorytm znajdujący pewne rozwiązanie w czasie tylko kwadratowo wiekszym. (Nie jest to cecha wszystkich problemów; np. znamy obecnie wielomianowy algorytm odpowiadający na pytanie, czy liczba jest złożona, ale nie znamy algorytmu znajdujacego w czasie wielomianowym nietrywialny dzielnik liczby złożonej.)  Po drugie, dla danego wartościowania
można oczywiście łatwo sprawdzić, czy spełnia ono daną formułę. Nasz algorytm, dla danej formuły A  przegląda kolejne maszyny Turinga (w ustalonym porządku) i symuluje je "ruchem zygzakowym", aż napotka wartościowanie spełniające formułę A (o ile jest spełnialna). Jeśli maszyna powiedzmy nr k produkuje takie wartosciowania w czasie p(n), to nasz algorytm będzie działał w czasie proporcjonalnym do p^2 (n).

Ograniczenie pamięciowe a problem stopu. Jeśli złożoność czasowa maszyny Turinga jest ograniczona funkcją T(n), to z definicji maszyna zatrzymuje się dla każdych danych. Dla ograniczonej złożonosci pamięciowej nie jest to takie oczywiste. Mamy jednak

Twierdzenie Spisera  Mając daną maszynę M o złożonosci pamięciowej ograniczonej przez S(n) można skonstruować maszyne M', która akceptuje ten sam język co M, ma tę samą złożoność pamięciową, a ponadto zatrzymuje się dla każdego słowa wejściowego.

Szkic dowodu.  Kluczowa jest obserwacja, że dla danej konfiguracji C rozmiaru K, wszystkie konfiguracje rozmiaru K, z których
można osiągnąć C tworzą drzewo (gdzie rodzic wierzchołka etykietowanego konfiguracją D jest etykietowany jedyną konfiguracją osiagalną  z D w jednym kroku,  a etykietą korzenia jest  C).  Przy pomocy odpowiednio dobranych stanów i przejść, maszyna M' może przeszukać to drzewo i sprawdzić, czy M mogłaby osiagnąć konfigurację C z konfiguracji początkowej -- używając jedynie pamieci K.  Zauważmy, że w danej chwili w pamięci maszyny przechowywana jest tylko jedna konfiguracja. W szczególności, konfiguracja C, od której zaczynamy przeszukiwanie, nie jest trzymana w pamięci, ale zostaje na końcu zrekonstruowana z powrotem.

Zalóżmy na chwilę, że maszyna M', otrzymując na wejściu słowo w, zna maksymalny rozmiar K konfiguracji osiągalnych przez maszynę M z konfiguracji początkowej (ze słowem w). Wtedy M' może przeglądać kolejno wszystkie konfiguracje rozmiaru K i sprawdzać, czy któraś z nich jest osiagalna z konfiguracji początkowej.

Problem w tym, że nie znamy rozmiaru K ! Można to jednak przezwyciężyć w podobny sposób.
Zaczynamy od K = 1. Jeśli dla jakiegoś K żadna konfiguracja akceptująca  nie jest osiągalna z poczatkowej w pamieci K, to w podobny sposób badamy te konfiguracje rozmiaru K, które w następnym kroku maszyna M "chciałaby powiekszyć"  do konfiguracji rozmiaru K+1 (może to mieć miejsce, gdy ze skrajnie prawej pozycji maszyna wykona kolejny ruch w prawo).

Jesli któraś z takich konfiguracji  jest osiagalna z początkowej, decydujemy powiekszyć pamięć, K := K+1. W przeciwnym razie M' kończy obliczenie bez akceptacji.  Szczegóły są ćwiczeniem z programowania maszyn Turinga. Z konstrukcji wynika, że M' używa nie więcej pamieci niż M.

27 lutego

W niedeterministycznej maszynie Turinga zamiast funkcji mamy relację. Z danej konfiguracji mamy na ogół wiele możliwych ruchów. Maszyna M akceptuje słowo w jeśli przynajmniej jedno obliczenie jest akceptujace. O maszynie niedeterministycznej mówimy, że działa w czasie ograniczonym przez T(n) (lub w pamięci ograniczonej przez S(n)), jeśli każde obliczenie na słowie wejsciowym długości n kończy się w co najwyżej T(n) krokach (lub wykorzystuje co najwyżej S(n) komórek pamieci).

W ogólności dowolną niedeterministyczną maszynę Turinga można symulować przez maszyne deterministyczną. Jednak pytanie, na ile efektywnie można to zrobić, pozostaje głównym nierozwiazanym zagadnieniem teorii złożonosci.

Dla deterministycznej maszyny M działającej w czasie T(n), dopełnienie języka L(M) można również rozpoznać w czasie T(n).  Dla maszyny niedeterministycznej przypuszczalnie tak nie jest.

Ma jednak miejsce dość zaskakujący fakt.

Twierdzenie Immermana- Szelepcsenyi'ego (1988).
Zakładamy, ze S(n) jest funkcją nie mniejszą niz log n i w pełni pamięciowo konstruowalną, tzn. istnieje deterministyczna maszyna, która dla dowolnego wejścia rozmiaru n odwiedza dokładnie n komórek pamieci (większość "sensownych" funkcji ma tę własność).

Mając daną niedeterministyczną maszynę Turinga M, która działa w pamięci ograniczomej przez S(n), można skonstruować maszynę (niedeterministyczną) M', która działa również w pamięci S(n) i rozpoznaje dopełnienie języka rozpoznawanego przez M.

W terminach klas złożoności można to zapisać równaniem

       NSPACE ( S(n) ) = co-NSPACE ( S(n) )

Uwaga. Twierdzenie to implikuje w szczególności, że języki kontekstowe są zamknięte na dopełnienie, co przez wiele lat stanowiło problem otwarty w teorii języków formalnych.

Szkic dowodu.  Tym razem kluczową obserwacją jest, że pomocna może być liczba wszystkich konfiguracji osiągalnych przez maszynę M z konfiguracji początkowej (w jakimkolwiek obliczeniu). Idea: wiedząc, że ta liczba jest K, przeglądamy kolejne konfiguracje badając (niedeterministycznie), czy są osiągalne.  Jeśli znaleźliśmy K konfiguracji osiągalnych (a więc wszystkie) i żadna nie jest akceptujaca, to mamy pewność że nasze słowo wejściowe nie jest akceptowane przez M.  Okazuje się, że podobna idea pozwala na obliczenie liczby konfiguracji osiągalnych w T krokach, jeśli znamy dokładną liczbę konfiguracji osiągalnych w T-1  krokach (dla T=0 ta liczba jest 1).  Znajdując kolejne wartości dla T = 0,1,2,...  (aż do ustabilizowania się), znajdujemy potrzebną wartość K.

Przedstawimy dwa niedeterministyczne algorytmy implementowalne na niedeterministycznej maszynie Turinga w pamięci S(n).  W algorytmach tych wykorzystujemy swobodnie daną niedeterministyczną maszynę M. Pierwszy algorytm (program główny) przyjmuje jako dane słowo w i liczbę K (binarnie) i ma tę własność, że o ile się zatrzymuje w stanie innym niż error, to daje poprawną odpowiedź na pytanie czy M nie akceptuje w, pod warunkiem że  K jest liczbą wszystkich konfiguracji osiągalnych przez maszynę M z konfiguracji początkowej ze słowem wejściowym w. Drugi algorytm jest procedurą obliczajacą liczbę K, tzn.  o ile się zatrzymuje w stanie innym niż error, to wynik jest liczbą wszystkich konfiguracji osiągalnych przez M ze słowa wyjściowego w (poniżej mówimy krótko "osiągalnych").

Program główny
wejście: słowo w długości n
Oblicz (K);
licznik := 0;
Przeglądaj wszystkie konfiguracje C maszyny M rozmiaru S(n) w porzadku leksykograficznym i wykonuj:
   Wykonuj  (niedeterministyczne) obliczenie maszyny M na słowie w
    jesli w trakcie obliczenia pojawi się konfiguracja akceptujaca, to STOP, Odpowiedź NIE   (* słowo w jest akceptowane przez M *)
    jeśli pojawi się C, ale C nie jest akceptujace, to
        licznik := licznik + 1;
Jesli licznik < K to STOP error
Jesli licznik = K to STOP,  Odpowiedź TAK
(* przeszukaliśmy wszystkie konfiguracje osiagalne i nie było wśród nich akceptującej, zatem w nie jest akceptowane M *)

Procedura Oblicz (K)
Koniec := false;
Czas := 0;
while not Koniec do
   if Czas = 0 then  K_e := K := 1 (* dokladnie jedna konfiguracja osiagalna w 0 krokach *)
   else (* K jest liczbą konfiguracji osiągalnych w =< Czas -- 1 krokach,
               K_e w dokładnie Czas -- 1 krokach *)
      old_K_e := K_e;
      K_e := 0;
      for  C := wszystkie konfiguracje maszyny M rozmiaru S(n) przegladane w porzadku leksykograficznym do
         (* chcemy sprawdzic, czy C jest osiagalne w dokladnie Czas  krokach *)
         licznik := 0;
         osiagalna := false;
         for D := wszystkie konfiguracje maszyny M rozmiaru S(n) przegladane w porzadku leksykograficznym do
            Wykonaj  (niedeterministyczne)  Czas -- 1 kroków obliczenia maszyny M na słowie w
            (* w jest daną programu głównego *)
            if   osiagniętą konfiguracją jest D then
                licznik := licznik +1;
                if  D -->  C   (* C osiagalna z D w jednym  kroku  *)  then osiagalna :=  true
         if osiagalna then K_e := K_e + 1  (* C jest osiagalna w dokładnie Czas krokach *) else
         if licznik < old_K_e then STOP error 
        (* w pętli "for D..." nie sprawdziliśmy wszystkich konfiguracji osiągalnych w Czas -- 1 krokach,
             więc nie mamy pewności czy C nie jest osiagalna *)
      K := K + K_e;
      if K_e = 0 then Koniec := true
      (* wszystkie konfiguracje osiagalne są osiągalne w =<  Czas -- 1 krokach, a zatem K jest
           liczbą wszystkich konfiguracji osiągalnych *)
      else Czas := Czas + 1