Języki, automaty i obliczenia/Wykład 13: Złożoność obliczeniowa.

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Sformułujemy definicje podstawowych klas złożoności w języku maszyn Turinga oraz metodę ich porównywania. Przeanalizujemy związki między rodziną języków określonych przez maszyny Turinga a rodziną języków typu (0) z hierarchii Chomsky'ego. Podamy dalsze własności języków kontekstowych i typu (0). Wprowadzimy pojęcie języka rekurencyjnie przeliczalnego oraz przedstawimy tezę Churcha. Następnie omówimy teoretyczne podstawy teorii rozstrzygalności oraz przeanalizujemy kilka problemów nierozstrzygalnych w teorii języków.


Klasy złożoności obliczeniowej

Jednym z podstawowych celów wprowadzania maszyn Turinga jest dążenie do formalnej definicji złożoności obliczeniowej. Na podstawie wcześniejszych uwag możemy utożsamiać akceptację słowa przez maszynę Turinga z jej zatrzymaniem się. Intuicyjnie, można takie zachowanie maszyny Turinga utożsamić z wykonaniem programu, który zwraca odpowiedź "Tak" na postawione przez nas pytanie.

Definicja 1.1

Ustalmy funkcje . Mówimy, że maszyna Turinga (deterministyczna lub niedeterministyczna) akceptuje słowo w czasie , jeśli istnieje ciąg konfiguracji takich, że , dla pewnych oraz dla .

Jeśli istnieje ciąg konfiguracji , gdzie , jest konfiguracją akceptującą (tzn. dla pewnych ) oraz dodatkowo , to mówimy, że maszyna akceptuje słowo w pamięci .

Mówimy, że język jest akceptowany w czasie (pamięci ), jeśli istnieje maszyna Turinga , dla której oraz każde słowo jest akceptowane w czasie (pamięci odpowiednio).

Uwaga 1.1

W niektórych podejściach wykorzystuje się, do definicji złożoności pamięciowej, tak zwanych maszyn Turinga off-line. Pomysł polega na tym, aby nie uwzględniać komórek taśmy, z których maszyna czytała informacje, a jedynie te, do których następował zapis. Dzięki temu zabiegowi można w sposób "rozsądny" mówić o akceptacji słowa w pamięci itp. W ujęciu prezentowanym w tym wykładzie zajmujemy się akceptacją w pamięci , dla , zatem nie ma potrzeby dodatkowego definiowania maszyn Turinga off-line.

Definicja 1.2

Oznaczmy przez oraz rodzinę języków akceptowanych w czasie i odpowiednio pamięci przez deterministyczną maszynę Turinga. Dla maszyn niedeterministycznych wprowadzamy w identyczny sposób klasy oraz .

Określamy następujące klasy złożoności (klasy języków):

Wprost z definicji otrzymujemy zależności P NP oraz PSPACE NPSPACE . W dalszej części wykładu udowodnimy kilka mniej oczywistych zależności.

Przykład 1.1

Rozważmy język:

Język P . Deterministyczna maszyna Turinga akceptująca taki język może wyglądać następująco (zaczynamy od konfiguracji ):

  1. Jeśli symbol pod głowicą, to zamień go na . Inaczej odrzuć.
  2. Przejdź od lewego ogranicznika do prawego, sprawdzając, czy po występuje lub , po tylko lub , a po kolejny symbol lub ogranicznik. Jeśli ta zależność nie jest spełniona, odrzuć. Gdy osiągniesz ogranicznik wykonaj następny krok.
  3. Gdy przed ogranicznikiem nie znajduje się symbol , odrzuć. W przeciwnym razie zamień symbol na , a następnie poruszaj się w lewo, aż dotrzesz do symbolu innego niż i .
  4. Jeśli symbol do którego dotarłeś to , zamień go na . Sprawdź symbol po lewej. Jeśli to , poruszaj się w prawo aż do ogranicznika. Następnie przejdź do kroku 3.
  5. Jeśli dotarłeś do symbolu , poruszaj się w lewo aż do ogranicznika. Zamień symbol przy ograniczniku na , a następnie idź w prawo, zamieniając wszystkie symbole na . Gdy dojdziesz do ogranicznika, przejdź do kroku .
  6. Jeśli dotarłeś do ogranicznika, oznacza to, że skasowano już wszystkie symbole . Przejdź w prawo aż do ogranicznika. Jeśli natrafisz na symbol , odrzuć. W przeciwnym przypadku, akceptuj.

Nietrudno zaobserwować, że maszyna przechodzi przez taśmę w prawo i w lewo tyle razy, ile symboli zawiera taśma oraz wykonuje jeden dodatkowy przebieg na starcie. Zatem słowa z są akceptowane w czasie ograniczonym wielomianowo.

Przykład 1.2

Rozważmy teraz język

Najprostszą metodą uzasadnienia, że NP jest konstrukcja tak zwanej wyroczni. Polega ona na następującej dwuetapowej procedurze:

  1. Skonstruuj niedeterministyczną maszynę Turinga (wyrocznia) generującą pewne słowo (certyfikat).
  2. Zweryfikuj w sposób deterministyczny spełnienie założeń przez certyfikat.

W naszym przykładzie Etap 1 wygląda następująco:

  1. Użyj dwóch taśm. Na pierwszej z nich znajduje się .
  2. Idź po pierwszej taśmie, wykorzystując niedeterministyczną funkcję przejść. Napotykając , możesz wypisać na taśmie drugiej i przejść o jedną komórkę w prawo na taśmie pierwszej lub przejść do następnego kroku. Jeśli dotarłeś do prawego ogranicznika taśmy pierwszej, przejdź do kroku 3.
  3. Powróć do początku pierwszej taśmy. Wykonaj sekwencję jak w kroku , z tą różnicą, że teraz na drugiej taśmie wypisuj symbole .
  4. Jako ostatnią część tego etapu przekopiuj symbole z pierwszej taśmy na drugą (po symbolach i ).

W konstrukcji wykorzystaliśmy dwie taśmy, ale oczywiście w nawiązaniu do wcześniejszych uwag, całą konstrukcję można wykonać na jednej taśmie (z odpowiednio rozszerzonym alfabetem i bardziej skomplikowaną funkcją przejść).

Etap 2 polega na weryfikacji, czy na taśmie drugiej znajduje się słowo postaci , gdzie oraz . Jeśli tak, to słowo wejściowe pochodziło z języka i akceptujemy. Można do tego wykorzystać deterministyczną maszynę Turinga, niemal identyczną z opisaną w przykładzie poprzednim.

Jeśli słowo wejściowe pochodzi z języka , to jedno z obliczeń maszyny niedeterministycznej z Etapu 1. prowadzi do konstrukcji odpowiedniego słowa na drugiej taśmie. Nie wiemy, jaka dokładnie ścieżka obliczeń ma być wykorzystana, ale dla akceptacji języka nie ma to znaczenia.

Zastanów się, czy da się wykazać, że także P (Ćwiczenie 1.3, do tego wykładu).

Definicja 1.3

Funkcja jest konstruowalna pamięciowo, jeśli istnieje maszyna Turinga , dla której , gdzie , dla , oraz dodatkowo jest konfiguracją końcową.

Inaczej mówiąc, funkcję nazywamy konstruowalną pamięciowo, jeśli istnieje maszyna Turinga , otrzymując na wejściu słowo długości , zaznacza na taśmie roboczej klatek i zatrzymuje się (akceptując słowo ).

Przykład 1.3

Funkcja jest konstruowalna pamięciowo. Maszyna , która konstruuje działa według schematu:

  1. Przejdź do prawego markera. Jeśli napotkano symbol inny niż , to odrzuć.
  2. Idź w lewo aż do pierwszego symbolu lub markera
  3. Jeśli napotkałeś symbol , zamień go na i przejdź do prawego markera. Dopisz do słowa symbol (zwiększając tym samym długość słowa na taśmie o ). Następnie powtórz cykl od .
  4. Jeśli napotkałeś marker, idź w prawo, zamieniając wszystkie wystąpienia na . Następnie wracaj do lewego markera i zatrzymaj się, akceptując.

Twierdzenie 1.1 liniowa kompresja pamięci

Niech będzie dany język oraz maszyna Turinga akceptująca w pamięci . Dla dowolnego istnieje maszyna Turinga akceptująca w pamięci .

Dowód

(Szkic) Ustalamy liczbę naturalną , dla której . Maszynę definiujemy następująco:

  1. Przekoduj słowo wejściowe, łącząc po kolejnych symboli w jeden blok stanowiący nowy symbol na taśmie.
  2. Symuluj maszynę na skompresowanej taśmie. Położenie głowicy wewnątrz bloku zakoduj w stanach maszyny .

Zauważmy, że w kroku . maszyna wykorzystuje komórek pamięci do odczytania słowa wejściowego. Kompresja taśmy zapewnia, że podczas symulowania maszyny nie wykorzystamy więcej niż komórek. Jednocześnie można założyć, że akceptuje słowa wejściowe z języka o długości mniejszej niż bez symulowania .

End of proof.gif

Twierdzenie 1.2 Savitch

Dla dowolnej funkcji konstruowalnej pamięciowo spełniającej warunek prawdziwa jest inkluzja .

Dowód

Niech będzie niedeterministyczną maszyną Turinga akceptującą język w pamięci . Niech oznacza liczbę konfiguracji potrzebną do zaakceptowania słowa o długości . Istnieje liczba , dla której , co z kolei oznacza, że każde słowo o długości jest akceptowane w krokach czasowych.

End of proof.gif

Rozważmy algorytm:

Algorytm


  1  Wejście: słowo  długości 
  2  oblicz 
  3  for każda konfiguracja akceptująca  dla której 
  4    do if Test(, , ) then akceptuj

gdzie procedura Test ma następującą postać:

Algorytm Procedure Test(,,)


  1  if  and [ () or ()] then return true
  2    else for każda konfiguracja  dla której 
  3      do if Test(,,) and Test ,,)
  4        then return true;
  5  return false

Przedstawiony algorytm można zrealizować za pomocą wielotaśmowej maszyny Turinga. Założenie dotyczące konstruowalności pamięciowej jest istotnie wykorzystywane w tej konstrukcji przy implementacji linii 3 algorytmu i linii 2 procedury Test. Musimy zaznaczyć komórek taśmy, aby móc konstruować konfiguracje o długości ograniczonej przez i móc następnie wykonywać na nich symulację maszyny .

Zauważmy, że ilość konfiguracji jest ograniczona przez , a głębokość rekursji przez . Oznacza to, że jesteśmy w stanie skonstruować maszynę Turinga, która wymaga pamięci, gdzie jest pewną stałą. Na mocy Twierdzenia 1.1 jesteśmy w stanie określić maszynę działającą w pamięci .

Wniosek 1.1

PSPACE NPSPACE

Lemat 1.1

Jeśli , to oraz .

Dowód

Niech będzie dana maszyna deterministyczna akceptująca dany język w czasie . Do akceptacji słowa o długości maszyna wykorzystuje co najwyżej kroków czasowych, czyli odwiedza co najwyżej komórek taśmy.

Na podstawie Twierdzenia 1.1 istnieje maszyna Turinga wykorzystująca

komórek pamięci. Dla niedeterministycznych maszyn Turinga argumentacja jest identyczna.

End of proof.gif

Wniosek 1.2

P NP PSPACE NPSPACE
Uwaga 1.2

Nie jest znany przykład wykazujący silną inkluzję P NP ani dowód wykluczający istnienie takiego przykładu. Powszechnie uznawana hipoteza głosi:

P NP.

Rozstrzygnięcie jej prawdziwości lub fałszywości stanowi jeden z najważniejszych, a zarazem najtrudniejszych problemów współczesnej informatyki. Jak widzieliśmy w Przykładzie 1.2, nawet w przypadku konkretnego języka NP, problem uzasadnienia, że także P, jest nietrywialny, gdyż wymaga zazwyczaj konstrukcji całkiem nowej maszyny Turinga niż ta do weryfikacji NP .

Redukcja i problemy zupełne

Definicja 2.1 transformacja wielomianowa

Niech będą dowolnymi językami nad pewnym alfabetem . Mówimy, że redukuje się do w czasie wielomianowym, co oznaczamy , gdy istnieje deterministyczna maszyna Turinga taka, że dla dowolnego istnieje i stan o własności

oraz

Lemat 2.1

Załóżmy, że . Wtedy zachodzą implikacje:

  1. P       P,
  2. NP       NP,
  3. PSPACE       PSPACE.

Dowód

Dane słowo transformujemy do w czasie wielomianowym, co gwarantuje założenie . Dzięki założeniu P możemy rozstrzygnąć, czy (tzn. jeśli akceptujemy , to robimy to w czasie wielomianowym). Tym sposobem (korzystając z definicji transformacji wielomianowej) akceptujemy w czasie wielomianowym, o ile tylko . Dowód dla pozostałych implikacji jest identyczny.

End of proof.gif

Definicja 2.2

Niech oznacza pewną klasę języków. Język nazywamy -trudnym, jeśli spełniony jest warunek:

Jeżeli dodatkowo spełniony jest warunek , to język nazywamy -zupełnym.

Intuicyjnie, fakt, że język jest -zupełny, oznacza, że jest on najbardziej skomplikowany (pod względem obliczeniowym) wśród języków z klasy , natomiast język -trudny jest bardziej skomplikowany niż każdy z klasy , choć sam nie musi do niej należeć.

Uwaga 2.1

Rozważając klasę P , NP i PSPACE, możemy mówić o językach (problemach) P -zupełnych, NP -zupełnych, czy też PSPACE -zupełnych. To samo odnosi się do języków trudnych (tzn. klasa języków P -trudnych, itd.).

Przykład 2.1

Rozważmy języki:

Języki: oraz wyglądają na bardzo podobne, zatem wydaje się, że oraz . Uzasadnienie tego faktu jest prawie natychmiastowe.

Konstruujemy deterministyczną maszynę Turinga która działa w następujący sposób:

  1. Jeśli słowo wejściowe jest puste, to stop.
  2. Przejdź do prawego ogranicznika. Jeśli przy ograniczniku nie występuje symbol , to wykonaj krok 1.
  3. Jeśli w słowie wejściowym występuje symbol , to sprawdź, czy słowo przetwarzane jest postaci , gdzie oraz oraz czy dodatkowo jest liczbą parzystą. Jeśli nie, to wykonaj krok 1.
  4. Zamień słowo na słowo i wykonaj krok 1.
  5. Przejdź nad pierwszy symbol po lewym ograniczniku i zatrzymaj się.

W ten sposób zawsze przeprowadzamy konfigurację na konfigurację , przy czym tylko, gdy . Zatem wtedy i tylko wtedy, gdy . Wykazaliśmy, że .

Warunek otrzymujemy w sposób identyczny. Trzeba tylko wypisać odpowiednią ilość symboli (a wiemy już, jak konstruować liczbę , mając dane ).