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

Ćwiczenia 13

Ćwiczenie 1

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L_1=\left\{www\: : \: w\in \left\{\circ,\bullet,\star\right\}^*\right\}. }

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

Ćwiczenie 2

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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ę ${𝒩}{ℳ}{𝒯}$ 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 3

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 4

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