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

Ćwiczenia 13

Ćwiczenie 1

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

$L=\{3^k:::k=i\cdot j\text{ dla pewnych }i,j>1\}$,

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

Uzasadnij, że także $L\in$ P ${\displaystyle }$.

Wskazówka

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

Rozwiązanie

Sprawdzamy wszystkie możliwości. Musimy wykonać maksymalnie $k^2$ (wielomianową ilość) mnożeń. Sama weryfikacja zależności $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 $1$ jest tylko do odczytu. Mamy na niej słowo $3^k$.
2. Rozpocznij od zapisania słowa $11$ na taśmie nr $2$ i słowa $22$ na taśmie nr $3$.
3. Przepisz słowa na taśmę nr $4$ według kolejności taśm $2,3,1$.
4. Sprawdź na taśmie nr $4$ czy $k=i\cdot j$. Jeśli tak, to akceptuj. Inaczej krok następny.
5. Dopisz symbol $1$ na taśmie nr $2$. Gdy powstało słowo dłuższe niż $k$, dopisz symbol $2$ na taśmie nr $3$, a słowo na taśmie nr $2$ usuń i zapisz na niej słowo $11$.
6. Jeśli słowo na taśmie nr $3$ jest dłuższe niż $k$, to odrzuć. W przeciwnym przypadku przejdź do kroku 3.

Idea tej maszyny jest bardzo prosta. Wykorzystaj taśmy nr $2$ (licznik 1) i $3$ (licznik 2) jako liczniki, a na taśmie $4$ wykonuj symulacje. Zacznij od stanu liczników na $2$ i zwiększaj kolejno licznik 1, a po jego przepełnieniu zeruj go (do wartości początkowej $2$) i zwiększ licznik $2$. Gdy on także się przepełni, to iloczyn stanów liczników przekracza $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 $n$). Dla małych $n$ możemy zawsze rozbudować maszynę tak, aby akceptowała słowa bez żadnego testowania. Zatem $L\in$ P .

Ćwiczenie 2

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

Wskazówka

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

Rozwiązanie

Bierzemy maszynę $M{T}_4$ z wykładu konstruującą funkcję $2n$. Dodajemy jedną dodatkową taśmę (oznaczmy taśmy przez $I$ oraz $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ę ${ℳ}$ według schematu:

1. Jeśli słowo wejściowe jest puste, to stop.
2. Jeśli słowo wejściowe jest inne niż $1^n$, to odrzuć.
3. Przepisz słowo wejściowe tak, aby znajdowało się na taśmie $I$, a taśma $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ę $S$.
5. Symulujemy maszynę $M{T}_4$ na taśmie $S$.
6. Dopisujemy do taśmy $S$ słowo wejściowe. W tym momencie zaznaczyliśmy dokładnie $3n$ komórek taśmy.
7. Zamieniamy symbole na $1$ (zapominamy o symulacji taśm), wracamy do lewego markera i przechodzimy do konfiguracji końcowej $s_1\in S_F$.

Po zakończeniu cyklu doszliśmy do konfiguracji $\mathrm{♯}{s}_1{1}^{3n}\mathrm{♯}$, co było wymagane w definicji.

Ćwiczenie 3

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

Wskazówka

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

Rozwiązanie

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

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

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

Po zakończeniu cyklu doszliśmy do konfiguracji $\mathrm{♯}{s}_1{1}^{3^n}\mathrm{♯}$, 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 ${ℳ}{𝒯}$ akceptującej język:

$L_1=\{www:::w\in {\{\circ ,\bullet ,\star \}}^{*}\}$

Zmodyfikuj, ewentualnie, tę konstrukcję ${ℳ}{𝒯}$, aby udowodnić $L_1\in$ P .

Ćwiczenie 5

Zadanie domowe - cwiczenie 7 - do wykładu 12 polegało na konstrukcji niedeterministycznej maszyny Turinga ${𝒩}{ℳ}{𝒯}$ akceptującej język:

$L_2=\{w_1{w}_1{w}_2{w}_2\dots w_n{w}_n:::w_i\in {\{\circ ,\bullet \}}^{+},n>0\}$

Zmodyfikuj, ewentualnie, tę konstrukcję ${𝒩}{ℳ}{𝒯}$ aby udowodnić, że $L_2\in$ NP .

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

ZADANIA DOMOWE

Ćwiczenie 6

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

Ćwiczenie 7

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