Matfyz Wiki

[Zap] 17.1.2011

anihilat0r at 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..