[Zk] 5.2.2009
Napsal: 5. 2. 2010 15:11
Dnes jsem úspěšně (JUCHŮŮŮŮŮ!!!!) zdolal zkoušku ze složitosti.
Otázky na písemku: 2R-SAT s co nejlepší složitostí (šlo lineárně vzhledem k počtu proměnných), dále SALBL \in co-NP úplné (převod ze SATu)
Ústní: Já měl Savičovu větu, zaslechl jsem ještě Cook Levina a SP pomocí VP.
K té savičově větě se ještě ptal, k čemu jsou potřeba ty předpoklady, což jsem přesně nevěděl. Takže tedy pro ostatní: Prostorová konstruovatelnost S(n) je potřeba na to, aby se všechny konfigurace daly procházet foreachem (kdybych nevěděl, že je to prostorově konstruovatelný, nevěděl bych, kolik prostoru to zabere aa tudíž bych si to pak nemoh hodit do nějakýho seznamu, kterej budu tim foreachem procházet). S(n) >= log(n) musí být proto, že by 2^dS(n) jinak mohlo být < n, tedy menší než zadání - což je nejmenší možná velikost konfigurací.
Dohromady sem řešil jen 3 otázky (2písemná + 1 ústní) => znamená to, že se složitost zkoušky ze složitosti snižuje?
(Pravda, měl jsem všechno +- dobře (=> 1 ), tak mi nedával žádný doplňující dotazy)
Jak dopadli ostatní?
Otázky na písemku: 2R-SAT s co nejlepší složitostí (šlo lineárně vzhledem k počtu proměnných), dále SALBL \in co-NP úplné (převod ze SATu)
Ústní: Já měl Savičovu větu, zaslechl jsem ještě Cook Levina a SP pomocí VP.
K té savičově větě se ještě ptal, k čemu jsou potřeba ty předpoklady, což jsem přesně nevěděl. Takže tedy pro ostatní: Prostorová konstruovatelnost S(n) je potřeba na to, aby se všechny konfigurace daly procházet foreachem (kdybych nevěděl, že je to prostorově konstruovatelný, nevěděl bych, kolik prostoru to zabere aa tudíž bych si to pak nemoh hodit do nějakýho seznamu, kterej budu tim foreachem procházet). S(n) >= log(n) musí být proto, že by 2^dS(n) jinak mohlo být < n, tedy menší než zadání - což je nejmenší možná velikost konfigurací.
Dohromady sem řešil jen 3 otázky (2písemná + 1 ústní) => znamená to, že se složitost zkoušky ze složitosti snižuje?
(Pravda, měl jsem všechno +- dobře (=> 1 ), tak mi nedával žádný doplňující dotazy)
Jak dopadli ostatní?