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ó x^f fordítottja az x betűinek fordított sorrendben való leírásával kapott szó. Például 11010^f=01011. Mutassuk meg, hogy van olyan c állandó, hogy |C(x)-C(x^f)|<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 a_i 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 V₁ ill. V₂ részre ( $V=V_1\cup V_2\mbox{ és } V_1\cap V_2=\emptyset$), hogy G-nek legfeljebb két V₁ és V₂ között menő éle (olyan, aminek az egyik végpontja V₁-be, a másik V₂-be esik) van! Bizonyítsuk be, hogy $L\in {\rm P}$!