Automaty Andrzej Szepietowski

[ Pobierz całość w formacie PDF ]

Działanie maszyny M można podzielić na dwa etapy:
" niedeterministyczne odgadywanie certyfikatu k,
" deterministyczne sprawdzenie, czy certyfikat jest poprawny, czy k dzieli n.
Ważne jest przy tym, że certyfikat nie jest długi, jest krótszy od słowa wejściowego, oraz
to, że czas drugiego etapu można ograniczyć przez wielomian od długości wejścia.
120 Rozdział 5. Czasowa złożoność obliczeniowa
Jako następny przykład rozważmy problem SAT. Wejściem problemu SAT jest formuła
boolowska � w koniunkcyjnej postaci normalnej, to znaczy jest koniunkcją klauzul
� = C1 '" C2 '" . . . '" Ck,
gdzie każda klauzula jest alternatywą literałów, a każdy literał to zmienna lub jej zaprze-
czenie. Na przykład formułą w postaci normalnej jest
(x1 (" �x2 (" x3) '" (�x2 (" x4 (" �x5) '" (�x1 (" x4).
Wyjściem problemu jest odpowiedz na pytanie, czy formuła jest spełnialna. Niedetermini-
styczna maszyna Turinga M akceptująca SAT posiada trzy taśmy. Na pierwszej znajduje
się wejście, czyli formuła. Na drugiej maszyna odgaduje ciąg liter T lub F jako odgadnię-
cie wartości podstawianych na kolejne zmienne występujące w formule. Następnie prze-
pisuje formułę na trzecią taśmę zastępując zmienne przez odpowiednie symbole T lub F .
Na koniec sprawdza, czy w każdej klauzuli przynajmniej jeden literał otrzymał wartość
True. Podobnie jak w poprzednim przykładzie obliczenie maszyny M można podzielić na
dwa etapy:
" niedeterministyczne odgadywanie certyfikatu, czyli podstawienia,
" deterministyczne sprawdzenie, czy certyfikat (podstawienie) jest poprawny, czy speł-
nia formułę.
Podobnie jak w poprzednim problemie certyfikat jest krótsze od formuły, a czas drugie-
go etapu można oszacować przez funkcję proporcjonalną do kwadratu długości formuły.
Okazuje się, że tak jest dla wszystkich problemów (języków) z klasy N P.
Twierdzenie 5.11 Język L jest akceptowany przez niedeterministyczną maszynę Turinga
M w czasie wielomianowym wtedy i tylko wtedy, gdy istnieje wielomian p oraz determini-
styczna maszyna Turinga MR działająca w czasie wielomianowym taka, że język L można
przedstawić w postaci
L = {w | "y |y| d" p(|w|) oraz w#y jest akceptowane przez MR}
Komentarz. Dla dowolnego słowa w, słowo y jest certyfikatem, zaś MR deterministyczną
maszyną sprawdzającą poprawność certyfikatu. Twierdzenie orzeka, że problemy z kla-
sy N P, to problemy z krótkimi (wielomianowej długości) certyfikatami oraz szybkimi
(działającymi w czasie wielomianowym) deterministycznymi algorytmami sprawdzający-
mi certyfikaty.
Dowód: Najpierw dowodzimy część "tylko wtedy". Zakładamy, że język L jest postaci
L = {w | "y |y| d" p(|w|) oraz w#y jest akceptowane przez MR}
5.6. Koszt determinizacji 121
Niedeterministyczna maszyna M akceptująca L na wejściu w odgaduje y długości |y| d"
p(|w|), a następnie symuluje maszynę MR na słowie w#y i akceptuje, jeżeli MR akceptu-
je. Maszyna M akceptuje te słowa wejściowe w, dla których istnieje odpowiedni certyfikat
y. Czas obliczenia można oszacować, przez
" p(|w|) potrzebne na odgadnięcie y,
" q(|w|+p(|w|)) czas symulacji MR; q oznacza wielomian, który ogranicza czas pracy
maszyny MR.
Całość można ograniczyć przez wielomian.
Teraz dowodzimy część "wtedy". Niech M będzie niedeterministyczną maszyną Tu-
ringa akceptującą język L i niech q będzie wielomianem ograniczającym jej czas. Dla
każdego słowa w akceptowanego przez M niech y będzie obliczeniem akceptującym ma-
szyny M na w, dokładniej y jest ciągiem konfiguracji wypisanych jedna za drugą,
y = �0#�1# . . . #�m, m
Ponieważ długość każdej konfiguracji z obliczenia można oszacować przez q(|w|), więc
całe y nie jest dłuższe od p(|w|) = q2(|w|). Istnieje także deterministyczna maszyna Turin-
ga MR, która w czasie wielomianowym sprawdzi, czy ciąg y jest poprawnym obliczeniem
akceptującym maszyny M na słowie wejściowym w. Maszyna MR działa następująco:
" sprawdza, czy �0 jest konfiguracją początkową,
" sprawdza, czu �i jest następnikiem �i-1, dla i = 1, . . . , m - 1,
" sprawdza, czy �m jest akceptująca.
Maszyna MR jest deterministyczna i działa w czasie wielomianowym. Możemy teraz
przedstawić L w postaci
L = {w | "y |y| d" p(|w|) oraz w#y jest akceptowane przez MR}.
5.6 Koszt determinizacji
W rozdziale o maszynach Turinga pokazaliśmy, że dla każdej niedeterministycznej ma-
szyny Turinga MN istnieje równoważna jej deterministyczna Maszyna Turinga MD. Przy-
pomnijmy, że maszyna MD wypisuje (bez powtórzeń) konfiguracje osiągalne przez MN z
122 Rozdział 5. Czasowa złożoność obliczeniowa
konfiguracji początkowej i sprawdza, czy wśród nich jest jakaś akceptująca. Zastanówmy
się, ile jest konfiguracji maszyny MN , której czas jest ograniczony przez T (n) e" n. Kon-
figuracja jest wyznaczona przez stan, pozycje głowic i zawartość taśm. Ich liczbę można
ograniczyć przez
|Q| � |�|kS(n) � S(n)k,
gdzie:
" |Q| jest liczbą stanów,
" S(n) ogranicza liczbę komórek zapisanych na każdej taśmie,
" |�| jest liczbą możliwych symboli na taśmie,
" k jest liczbą taśm.
Liczbę możliwych konfiguracji można ograniczyć, przez
dS(n)
dla stałej d = |Q| � |�|2k. Liczbę S(n) zużytych komórek na taśmach można ograniczyć
przez T (n), ponieważ zapisanie każdej nowej komórki wymaga przynajmniej jednego do-
datkowego kroku. Tak więc liczbę konfiguracji maszyny MN można ograniczyć przez
dT (n), a czas działania maszyny MD przez d2�T (n).
Z tego wynika, że jeżeli MN działa w czasie ograniczonym przez funkcję T (n), to MD
działa w czasie ograniczonym przez funkcję cT (n) dla pewnej stałej c zależnej od maszyny
MN. Tak więc ten sposób determinizacji maszyn Turinga powoduje wykładniczy wzrost
złożoności czasowej.
Twierdzenie 5.12 Dla każdej niedeterministycznej maszyny Turinga MN z czasem ogra-
niczonym przez funkcję T (n) e" n istnieje równoważna jej deterministyczna maszyna
Turinga MD z czasem ograniczonym przez funkcję cT (n) dla pewnej stałej c zależnej od
maszyny MN .
5.7 Problemy N P zupełne
Oczywiście zachodzi zawieranie P �" N P ponieważ każda deterministyczna maszyna
Turinga jest także niedeterministyczną maszyną. Nie wiadomo, czy zachodzi zawieranie
odwrotne (jest to najsłynniejszy problem otwarty w informatyce). Wiadomo natomiast, że
można porównywać trudność problemów i że istnieją problemy najtrudniejsze w klasie
N P.
5.7. Problemy N P zupełne 123
Definicja 5.13 Niech L �" �" oraz K �" "" będą dwoma językami. Powiemy, że L redu-
kuje się w czasie wielomianowym do K, co będziemy oznaczać przez
L d"p K,
jeżeli istnieje funkcja f obliczalna przez deterministyczną maszynę Turinga w czasie wie-
lomianowym taka, że dla każdego w " �"
w " L �! f(w) " K.
Mówiąc mniej formalnie istnienie redukcji oznacza, że język L nie jest trudniejszy
od języka K, bo jeżli mamy wielomianowy algorytm rozpoznający K, to mamy także
wielomianowy algorytm rozpoznający L.
Lemat 5.14 Jeżeli L d"p K oraz K " P, to L " P.
Dowód. Załóżmy, że mamy deterministyczną maszynę M1 akceptującą K w czasie ogra-
niczonym przez wielomian p oraz deterministyczną maszynę M2 redukującą L do K w
czasie ograniczonym przez wielomian q. Opiszemy teraz deterministyczną maszynę M3
akceptującą L. Na słowie wejściowym w maszyna M3 najpierw symulując M2 oblicza
f(w) a następnie symuluje M1 na słowie f(w). Długość słowa f(w) można oszacować
przez czas działania maszyny redukującej, czyli przez q(|w|). To daje oszacowanie czasu
obliczenia maszyny M3 przez
q(|w|) + p(q(|w|)).
Zadanie 5.15 Udowodnij, że jeżeli L d"p K oraz K " N P, to L " N P.
Definicja 5.16 Powiemy, że język K jest N P trudny, jeżeli każdy język L " N P redukuje [ Pobierz całość w formacie PDF ]

Podobne