zapocet 27.10

1. Popiste TS ktory pocita funkci $\left\lceil \log _2 x \right\rceil$

2. Ukazte, ze funkce x mod y je PRF, pri odvozovani mozete predpokladat, ze scitanie, odcitanie, nasobenie, sign a konstanta su PRF

3. Ukazte, ze existuje PRF f(x,y), pre ktoru plati, ze

$$\varphi _{f(x,y)}(a,b) = \varphi _x (a) . \varphi _y (b)$$

4. Ukazte ze KLIKA je NP uplny problem pomocou problemu ktoreho tazkost bola ukazana na prednaske.

Ahoj,

k tej 3 ulohe, to je zrejme uloha na smn vetu, je toto validne riesenie?

Nech e je Godelove cislo take ze $\varphi_e^{(4)} (x,y,a,b) \simeq \varphi_x(a).\varphi_y(b)$
potom podla smn plati $\varphi_e^{(4)} (x,y,a,b) = \varphi_{f(x,y)}^{(2)}(a,b)$
kde $f(x,y)=s(e,x,y)$