[Zap] 17.1.2011

anihilat0r

[Zap] 17.1.2011

Příspěvek od anihilat0r »

Otazky z dnesneho zapoctu:

1) Ukazte, ze TS s 1-smerne nekonecnou paskou je ekvivalentny s klasickym TS.
2) PRF f(x,y) = xy
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..
Odpovědět

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