Fórum studentů MFF UK

Ahoj, nevíte někdo, jak řešit příklad (2). Zkoušel jsem větu o rekurzi, pak i její verzi s parametrem, ale zatím se mi nepodařilo dospět k výsledku. Myslím si, že přes tu větu o rekurzi to nějak musí jít. Mám problém s tím číslem k. To [latex]$W_x = \{p_x^k|k \ge 0\}$[/latex] vypadá jako sjednocení množin [latex]$\{p_x^k\}$[/latex] přes všechna k. Ale nekonečné sjednocení asi nebude obecně rekurzivní. Díky. Pokud se mi podaří to vyřešit, řešení pošlu.

ja len dodam, ze ten 2SAT nevyriesil nik, tak ho ani nepocital, na ustnej som dostal dokaz Riceovej vety pomocou 1 prevoditelnosti a dokaz vety 17.8 ... skusal na chodbe, dost vela casu stravil v kancelarii.

sakra, nekdo me predbehl:)

tak pridam jen poznamky:
3. byl chytak - odpoved je ze halting problem JE zastavitelny (nas stolni PC ma omezenou pamet, disk, registry atd -> E jen konecne mnozstvi jeho ruznych konfiguraci -> lze detekovat zacykleni)
5. lze udajne najit nekde na webu v minulych pisemkach ze Slozitosti

jinak na ustni prevod CRF -> TS a 3 SAT je NP uplny -
celkova uspesnost byla podle me docela vysoka, videl jsem 2x 4, hodne jednicek, semtam 2 nebo 3...

Hodne stesti ostatnim
Lada

[b]Skuskovy test, 28/01/2010[/b]

(1) Ukazte, ze mnozina P = {p | p je prvocislo} ma primitivne rekurzivnu charakteristicku funkciu. Pri odvodzovani mozete vyuzit toho, ze scitanie, odcitanie, nasobenie, delenie, <, >, = su PRF a PRP

(2) Dokazte, ze existuje n, pre ktore plati, ze [latex]W_{n} = \{p_{n}^{k} | k >= 0\}[/latex]

(3) Rozhodnete, zda nasledujici verze halting problemu je algoritmicky rozhodnutelna. Je dan kod programu a ptame se, zda se tento program zastavi na pocitaci, ktery mame na stole.

(4) Ukazte, ze nasledujuci problem je NP-uplny:
i: Mnozina X, |X| = 3q a mnozina trojic C z X x X x X
p: Existuje C' z C taka, ze kazdy prvok z X sa vyskytuje v prave jedne trojici z C'?

(5) Popiste polynomialny algoritmus pre 2SAT (Formula v KNF, kde kazda klauzula ma prave 2 literaly)