A mai gyakorlat anyaga a Kolmogorov bonyolultság és a tár és időosztályok, különösen a P és az NP voltak. Az előadás még megy tovább, de gyakorlat már nem lesz a hátralevő másfél hétben. Viszont olyan dolgok lesznek előadáson, amik könnyen lehetnek vizsgán feladat formájában. Ezért a következő heti pótgyakorlaton új témájú feladatok várhatók, aki tud, mindenképpen jöjjön el. Ezen feladatok anyaga: Karp redukció, NP-teljesség. A mai feladatok pedig itt vannak: Algoritmuselmélet gyakorlat (7) 1. Jelölje |x|, ill. C(x) az $x\in \{0,1\}^*$ szó hosszát, ill. Kolmogorov-bonyolultságát. Bizonyítsuk be, hogy: (a) $x\in\{0,1\}^*,\;\vert x\vert=n$ és x-ben pontosan 20 db 1-es van $\Longrightarrow$ $C(x)\leq c\log n$ alkalmas c konstansra. (b) $\not\exists$ TG, mely n inputtal olyan n hosszú $x\in \{0,1\}^*$ szót számol ki, melyre $C(x)>2\log n$. (c) $\exists x\in\{0,1\}^*,\; \vert x\vert=n,\; C(x)\geq n-1,$ és x 0-val kezdődik. (d) $\exists x,y\in\{0,1\}^*,\; C(x)>C(xy)$. "A Kolmogorov-bonyolultság nem monoton a prefixeken." 2. Az $x\in I^*$ szó xf fordítottja az x betűinek fordított sorrendben való leírásával kapott szó. Például 11010f=01011. Mutassuk meg, hogy van olyan c állandó, hogy |C(x)-C(xf)|<c teljesül minden $x\in I^*$ szóra! 3. Igazoljuk, hogy tetszőleges n természetes számhoz megadható olyan $x\in \{0,1\}^*$ szó, melyre teljesül, hogy $\mid x\mid >n$ és $C(x)<0,5\log _2 \mid x \mid$. 4. Legyen $I=\{0,1\}$. A $H: I^*\rightarrow Z^+$ függvény az $x\in I^*$ szóhoz azon $y\in I^*$ összenyomhatatlan szavak számát rendeli, amelyek a kanonikus sorrendben megelőzik x-et. Igaz-e, hogy H rekurzív függvény? 5. Igazoljuk, hogy ha $L \subseteq I^*$ egy véges nyelv, akkor L felismerhető egy O(n) időkorlátos TG-vel. 6. Tegyük fel, hogy van egy olyan K nevű eljárás, mely (egyetlen lépésben) megmondja, hogy az inputjaként magadott irányítatlan gráf színezhető-e három színnel. Csináljunk egy a K eljárást használó algoritmust, mely polinomidőben megadja az input G gráf egy 3-színezését, ha $G\in 3-\mbox{\it SZÍN}$. 7. Egy $L \subseteq I^*$ nyelv esetén az L* nyelv definíciója a következő: $L^*=\{ x\in I^*;$ és van olyan $k\geq0$ egész és $x_1,\ldots ,x_k\in L$ hogy $x=x_1x_2\cdots x_k \}$. Igazoljuk, hogy ha $L\in NP$, akkor $L^*\in NP$. 8. Igazoljuk, hogy az alábbi L nyelv NP-ben van: $L=\{ f(x)=a_0+a_1x+a_2x^2+\cdots +a_nx^n;~ a_i\in Z$ és az f(x)=0 egyenletnek van egész megoldása $\}$. Megjegyzés: az ai számokat az inputban binárisan ábrázoljuk. 9. Álljon az L nyelv azon G=G(V,E) irányítatlan gráfokból, melyeknek a V csúcshalmaza felosztható két olyan nemüres V1 ill. V2 részre ( $V=V_1\cup V_2\mbox{ és } V_1\cap V_2=\emptyset$), hogy G-nek legfeljebb két V1 és V2 között menő éle (olyan, aminek az egyik végpontja V1-be, a másik V2-be esik) van! Bizonyítsuk be, hogy $L\in {\rm P}$! Megoldások