zapocet 27.10

Návštěvník

zapocet 27.10

Příspěvek od Návštěvník »

1. Popiste TS ktory pocita funkci \lceil \log _2 \left 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.
Pakluc

Re: zapocet 27.10

Příspěvek od Pakluc »

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)$
Odpovědět

Zpět na „NTIN090 Základy složitosti a vyčíslitelnosti“