Matfyz Wiki

[Zk] 8.2.2010

Kudo at 2010-02-08 16:35:35

Prikladam skusku zo slozitosti Verze G.

  1. Stacilo pouzit Riceovu vetu.

  2. S -> Tot to je identita. Opacne trebalo najst funkciu, ktora upravi ORF fci, aby vracala iba 0 alebo 1.

  3. Priklad na pouzitie smn vety

  4. Postupne odoberat vrcholy a skusat ci je velikosti k, ak je tak ten vrchol nepatril do VP. Ak nie je tak patril. Pokial patril, tak zmensit k, cez ktore testujem.

  5. nemal som (ked tak niekto doplnte)

Ustna:

  1. Dokaz Riceovej vety pomocou vety o rekurzi.

  2. dokazat NP uplnost 3SATu.

Mal som 4 priklady z 5.
Na ustnej som dokazy vedel.
Pan Kucera sa tvaril znudene, ked som mu to hovoril a pri 3SATe to uz ani nechcel rozoberat pre vsetky pripady. Ukazal som mu ako to funguje kre k>3, iba pre jeden smer.

Skuska celkom v pohode, ale je potreba sa orientovat v pojmoch. Najme co znamena W<sub>e</sub> a pod.
Potom sa tie priklady daju vymysliet. Na ustnej bol v pohode.

Na skusku som sa v podstate ucil len z jeho poznamok. A tie mi uplne stacili.

Attachments:

Xerxes at 2010-02-08 23:26:50

Doplňuji, možná trochu podrobněji (třeba se to někomu bude hodit):

  1. Množina S není rekurzivní. Zdůvodnění: buď C třída takových ČRF, které tvoří charakteristickou funkci nějaké rekurzivní množiny (čili jde o ORF s oborem hodnot {0, 1}). Potom zřejmě C neobsahuje všechny ČRF ani není prázdná, podle Riceovy věty tedy nemůže být množina A<sub>C</sub> = S rekurzivní.

  2. Osobně si myslím, že pro převod S -> Tot nelze identitu použít. Musí totiž platit x e S <=> f(x) e Tot a identita splňuje jen dopřednou implikaci (pokud x není z S, stále může být totální - např. funkce f(n) = n je totální, ale není z množiny S, protože nemá jako obor hodnot {0, 1}). Já jsem použil funkci f(x) takovou, že:

φf(x)(y)≃ψ(x,y)≃μz[φx(y)=0∨φx(y)=1]\varphi_{f(x)}(y) \simeq \psi(x, y) \simeq \mu z[\varphi_x(y) = 0 \vee \varphi_x(y) = 1]

Je třeba použít s-m-n větu. Nevím, na kolik si pan Kučera potrpí na formalizmus... když tak můžu rozepsat, ale teď moc se mi nechce. Pro převod Tot -> S jsem použil f(x) takovou, že:

φf(x)(y)≃ψ(x,y)≃sign(φx(y))\varphi_{f(x)}(y) \simeq \psi(x, y) \simeq sign(\varphi_x(y))

  1. Zaveďme f(x) tak, že:

φf(e)(x)≃ψ(e,x)≃μy[φe(x)=1]\varphi_{f(e)}(x) \simeq \psi(e, x) \simeq \mu y[\varphi_e(x) = 1]

Potom f je PRF dle s-m-n věty. Buď e z množiny S a fí(e) nechť je charakteristická funkce rekurzivní množiny A. Potom:

x∈A⇔φe(x)=1⇔ψ(e,x) ⁣ ⁣↓ ⇔φf(e)(x) ⁣ ⁣↓ ⇔x∈Wf(e)x \in A \Leftrightarrow \varphi_e(x) = 1 \Leftrightarrow \psi(e, x)\!\!\downarrow\,\Leftrightarrow \varphi_{f(e)}(x)\!\!\downarrow\,\Leftrightarrow x \in W_{f(e)}

čili W<sub>f(e)</sub> = A.

  1. Toto jsem řešil postupným přidáváním "ocásků" k jednotlivým vrcholům (po každém kroku: pokud volání černé skříňky řekne ANO, vrchol zahrnu do VP a ocásek nechám, jinak jej zase oddělám).

  2. Zřejmě jde o problém z NP (ověření je polynomiální). NP-těžkost lze ukázat triviálním převodem z problému 3DM. Stačí za každou trojici (w, x, y) vzít množinu {w, x, y} a za k položit q. Potom pokud je původní instance 3DM řešitelná, jsou příslušné množiny odpovídající zvoleným trojicím vzájemně disjunktní a je jich k. Naopak pokud nalezneme alespoň k vzájemně disjunktních množin, musí jich být právě q (vynucuje to velikost |W| = |X| = |Y| = q) a odpovídající trojice pak zřejmě tvoří perfektní párování.

Na ústní jsem dostal:

  1. K a K<sub>0</sub> - dokázat, že jsou RS, nejsou R a jsou 1-úplné.

  2. Dokázat, že SAT je NP-úplný.