# zapocet 27.10

<{ForumPost(poster="Anonymous", timestamp=2011-01-27 10:42:43)}>
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.
<{/ForumPost}>

<{ForumPost(poster="Pakluc", timestamp=2012-01-08 22:26:00)}>
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)$
<{/ForumPost}>