# [Zap] 17.1.2011

<{ForumPost(poster="anihilat0r", timestamp=2011-01-17 15:47:42)}>
Otazky z dnesneho zapoctu:  
  
1) Ukazte, ze TS s 1-smerne nekonecnou paskou  je ekvivalentny s klasickym TS.  
2) PRF f(x,y) = x<sup>y</sup>  
3) Ukazte, ze HC(s,t) je NP-uplny  
4) Ukazte, ze otazka (Existuje take ohodnotenie v)(Phi(v) = 0), kde Phi je KNF, patri do P.  
  
Ad 4) Tip: Take ohodnotenie samozrejme existuje vzdy...  
  
Nic horibilne, mne osobne neuznal prevod HC(s,t), kedze som si ho nepamatal/nevedel cely formalne, iba popis.. kto chodil na prednasky, by s tym ale problem mat nemal..
<{/ForumPost}>