navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m01tal:zkouska-2012-06-05 [2012/06/17 13:30] corvus |
courses:a4m01tal:zkouska-2012-06-05 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 20: | Řádek 20: | ||
| d) Definujte co-NP + jaký je vztah co-NP a ZPP. | d) Definujte co-NP + jaký je vztah co-NP a ZPP. | ||
| e) Zadány úlohy U, V, W. Platí U <| V <| W (<| je polynomiální redukce). U je 2-barevnost, W je existence hamiltonovské kružnice, V se neví. Napište nejsilnější tvrzení, které platí pro úlohu V a zdůvodněte. | e) Zadány úlohy U, V, W. Platí U <| V <| W (<| je polynomiální redukce). U je 2-barevnost, W je existence hamiltonovské kružnice, V se neví. Napište nejsilnější tvrzení, které platí pro úlohu V a zdůvodněte. | ||
| - | f) Popište vzájemné vztahy R, coR, RE, coRE, VS (mnozina vsech jazyku) a zduvodnete. (10b) | + | f) Popište vzájemné vztahy R (rekurzivní jazyky), co-R (doplňkové jazyky k R), RE, co-RE, VS (množina všech jazyků) a zdůvodněte. (10b) |
| ~~DISCUSSION~~ | ~~DISCUSSION~~ | ||
