zapocet 27.10

zapocet 27.10

Příspěvekod Návštěvník » 27. 1. 2011 10:42

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.
Návštěvník
 

Re: zapocet 27.10

Příspěvekod Pakluc » 8. 1. 2012 22:26

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)$
Pakluc
 


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

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron