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

From Studia Informatyczne

Ćwiczenia 13

Ćwiczenie 1

W trakcie wykładu rozważaliśmy język

\displaystyle  L=\left\{3^k\: : \: k=i\cdot j dla pewnych \displaystyle   i,j> 1\right\},

wykazując, że \displaystyle L\in NP .

Uzasadnij, że także
\displaystyle L\in P \displaystyle  .

Wskazówka

Zastanów się, ile maksymalnie trzeba wykonać mnożeń, aby zweryfikować istnienie \displaystyle i,j>1, dla których \displaystyle k=i\cdot j.

Rozwiązanie

Sprawdzamy wszystkie możliwości. Musimy wykonać maksymalnie \displaystyle k^2 (wielomianową ilość) mnożeń. Sama weryfikacja zależności \displaystyle k=i\cdot j (według uzasadnienia z wykładu) jest wykonywana w czasie wielomianowym.

Pozostaje zaprojektować deterministyczną maszynę generującą ciągi. Można to zrobić według schematu

(maszyna czterotaśmowa):

  1. Taśma nr \displaystyle 1 jest tylko do odczytu. Mamy na niej słowo \displaystyle 3^k.
  2. Rozpocznij od zapisania słowa \displaystyle 11 na taśmie nr \displaystyle 2 i słowa \displaystyle 22 na taśmie nr \displaystyle 3.
  3. Przepisz słowa na taśmę nr \displaystyle 4 według kolejności taśm \displaystyle 2,3,1.
  4. Sprawdź na taśmie nr \displaystyle 4 czy \displaystyle k=i\cdot j. Jeśli tak, to akceptuj. Inaczej krok następny.
  5. Dopisz symbol \displaystyle 1 na taśmie nr \displaystyle 2. Gdy powstało słowo dłuższe niż \displaystyle k, dopisz symbol \displaystyle 2 na taśmie nr \displaystyle 3, a słowo na taśmie nr \displaystyle 2 usuń i zapisz na niej słowo \displaystyle 11.
  6. Jeśli słowo na taśmie nr \displaystyle 3 jest dłuższe niż \displaystyle k, to odrzuć. W przeciwnym przypadku przejdź do kroku 3.

Idea tej maszyny jest bardzo prosta. Wykorzystaj taśmy nr \displaystyle 2 (licznik 1) i \displaystyle 3 (licznik 2) jako liczniki, a na taśmie \displaystyle 4 wykonuj symulacje. Zacznij od stanu liczników na \displaystyle 2 i zwiększaj kolejno licznik 1, a po jego przepełnieniu zeruj go (do wartości początkowej \displaystyle 2) i zwiększ licznik \displaystyle 2. Gdy on także się przepełni, to iloczyn stanów liczników przekracza \displaystyle k, zatem można zakończyć generowanie ciągów.

W oczywisty sposób otrzymujemy, że ilość wymaganych kroków czasowych maszyny jest ograniczona przez wielomian (dla dużych \displaystyle n).

Dla małych \displaystyle n możemy zawsze rozbudować maszynę tak, aby akceptowała słowa bez żadnego testowania. Zatem \displaystyle L\in P .

Ćwiczenie 2

Uzasadnij, że funkcja \displaystyle s(n)=3n jest konstruowalna pamięciowo.

Wskazówka

Przypomnij sobie uzasadnienie dla funkcji \displaystyle 2n z wykładu.

Rozwiązanie

Bierzemy maszynę \displaystyle MT_4 z wykładu konstruującą funkcję \displaystyle 2n. Dodajemy jedną dodatkową taśmę (oznaczmy taśmy przez \displaystyle I oraz \displaystyle S). Drugą taśmę realizujemy poprzez rozszerzenie alfabetu. Jest to spowodowane faktem, że w definicji konstruowalności pamięciowej wymagane jest istnienie jednotaśmowej deterministycznej maszyny Turinga. Konstruujemy maszynę \displaystyle \mathcal{M} według schematu:

  1. Jeśli słowo wejściowe jest puste, to stop.
  2. Jeśli słowo wejściowe jest inne niż \displaystyle 1^n, to odrzuć.
  3. Przepisz słowo wejściowe tak, aby znajdowało się na taśmie \displaystyle I, a taśma \displaystyle S była pusta (gdy zaczynamy symulować dwie taśmy musimy przejść do innego zestawu symboli, w którym rozróżniamy taśmy).
  4. Kopiujemy słowo wejściowe na taśmę \displaystyle S.
  5. Symulujemy maszynę \displaystyle MT_4 na taśmie \displaystyle S.
  6. Dopisujemy do taśmy \displaystyle S słowo wejściowe. W tym momencie zaznaczyliśmy dokładnie \displaystyle 3n komórek taśmy.
  7. Zamieniamy symbole na \displaystyle 1 (zapominamy o symulacji taśm), wracamy do lewego markera i przechodzimy do konfiguracji końcowej \displaystyle s_1\in S_F.

Po zakończeniu cyklu doszliśmy do konfiguracji \displaystyle \sharp s_1 1^{3n} \sharp, co było wymagane w definicji.

Ćwiczenie 3

Uzasadnij, że funkcja \displaystyle s(n)=3^n jest konstruowalna pamięciowo.

Wskazówka

Wykorzystaj konstruowalność pamięciową funkcji \displaystyle g(n)=3n.

Rozwiązanie

Wykorzystujemy trzy taśmy (\displaystyle I, \displaystyle C, \displaystyle S) oraz maszynę \displaystyle \mathcal{M} konstruującą pamięciowo funkcję \displaystyle g(n)=3n. Docelowa maszyna \displaystyle \mathcal{N} działa według schematu.

  1. Jeśli słowo początkowe jest puste, wypisz \displaystyle 1 i zatrzymaj się. W przeciwnym wypadku, wykonaj następny krok.
  2. Jeśli słowo wejściowe jest inne niż \displaystyle 1^n, to odrzuć.
  3. Na taśmie \displaystyle I wypisz słowo wejściowe, na taśmach \displaystyle C i \displaystyle S wypisz słowo \displaystyle 1.
  4. Wykonaj symulację maszyny \displaystyle \mathcal{M} na taśmie \displaystyle S oraz dopisz symbol \displaystyle 1 do taśmy \displaystyle C (po jednym przebiegu ilość symboli na taśmie \displaystyle S wzrasta trzykrotnie)
  5. Jeśli słowo na taśmie \displaystyle C jest krótsze niż słowo na taśmie \displaystyle I, wykonaj ponownie krok 4.
  6. W tym momencie na taśmie \displaystyle S zostało zaznaczone \displaystyle 3^n komórek.

Zamieniamy wypisane symbole na \displaystyle 1 (zapominamy o symulacji taśm), wracamy nad pierwszy symbol (przed lewym markerem) i przechodzimy do konfiguracji końcowej \displaystyle s_1\in S_F.

Po zakończeniu cyklu doszliśmy do konfiguracji \displaystyle \sharp s_1 1^{3^n} \sharp, co było wymagane w definicji konstruowalności

pamięciowej.


Ćwiczenie 4

Zadanie domowe - cwiczenie 6 - do wykładu 12 polegało na konstrukcji maszyny Turinga \displaystyle \mathcal{MT} akceptującej język:

\displaystyle  L_1=\left\{www\: : \: w\in \left\{\circ,\bullet,\star\right\}^*\right\}.

Zmodyfikuj, ewentualnie, tę konstrukcję \displaystyle \mathcal{MT}, aby udowodnić \displaystyle L_1 \in P .

Ćwiczenie 5

Zadanie domowe - cwiczenie 7 - do wykładu 12 polegało na konstrukcji niedeterministycznej maszyny Turinga \displaystyle \mathcal{NMT} akceptującej język:

\displaystyle  L_2=\left\{w_1 w_1 w_2 w_2 \dots w_n w_n \: : \: w_i \in \left\{\circ,\bullet\right\}^+, n>0 \right\}.

Zmodyfikuj, ewentualnie, tę konstrukcję \displaystyle \mathcal{NMT} aby udowodnić, że \displaystyle L_2 \in NP .

Podpowiedź: wykorzystaj konstrukcję z wyrocznią. Dla słowa wejściowego \displaystyle w przeprowadź weryfikację w trzech etapach: konstrukcja słów \displaystyle w_1, \dots ,w_n, gdzie \displaystyle n< |w| (wyrocznia), sklejanie, weryfikacja, czy \displaystyle w=w_1w_1 w_2 w_2 \dots w_n w_n.


ZADANIA DOMOWE


Ćwiczenie 6

Uzasadnij, że jeśli funkcja \displaystyle s(n) jest konstruowalna pamięciowo, to obliczenie \displaystyle d_1 \mapsto^* d_2 z definicji konstruowalności pamięciowej (tzn. \displaystyle d_1=\sharp s_0 1^n \sharp, \displaystyle d_2=\sharp s_1 1^{s(n)} w \sharp) następuje w co najwyżej \displaystyle c 2^{s(n)} krokach, gdzie \displaystyle c jest pewną stałą niezależną od \displaystyle n.
Podpowiedź: przeanalizuj ilość możliwych konfiguracji.

Ćwiczenie 7

Uzasadnij, że funkcja \displaystyle n^3 jest konstruowalna pamięciowo.