Zkouska 2010-02-04

Verze F:

1. Rozhodnete, zda mnozina $$S = \{ e | W_e \text{ obsahuje nejake prvocislo} \}$$ je rekurzivni, sve rozhodnuti zduvodnete.

2. Ukazte, ze mnozina S z predchoziho prikladu je rekurzivne spocetna.

3. Ukazde, ze $$DSPACE(\log_2 n) \subseteq P$$.

4. Ukazte, ze nasledujici problem je polynomialne resitelny:

Omezeny soucet podmnoziny

Instance: Mnozina n prvku A, s kazdym prvkem $$a \in A$$ asociovana velikost $$v(a) \in \{0,\ldots,n\}$$, cislo $$B \ge 0$$.
Otazka: Existuje mnozina prvku $$A' \subseteq A$$, pro niz plati, ze $$\sum_{a \in A'} v(a) = B$$?

5. S pomoci nektereho problemu probiraneho na prednasce ukazte, ze nasledujici problem je NP-uplny:

Nejvetsi spolecny podgraf

Instance: Grafy $$G_1 = (V_1, E_1)$$ a $$G_2 = (V_2, E_2)$$, prirozene cislo $$k \ge 0$$.
Otazka: Existuji mnoziny hran $$E'_1 \subseteq E_1$$ a $$E'_2 \subseteq E_2$$, $$|E'_1| = |E'_2| \ge k$$, pro nez jsou grafy $$G'_1 = (V_1, E'_1)$$ a $$G'_2 = (V_2, E'_2)$$ izomorfni? (Izomorfni = "vypadaji stejne").

K tomu rovnou reseni:

1. Rovnou z Riceovy vety (snad se ani nemuselo ukazovat, ze to neni trivialni trida funkci).

2. ja to psal jak odukaz prevodu z K, coz bylo spatne.

3. Snadno, viz odhad, ze TS v case $$n^i$$ popise max. $$n^i$$ pasky, takze $$\rightarrow DSPACE(n^i) \subseteq DTIME(n^i)$$ a zaroven $$\exists i \in \mathbb{N}: \log_2 n \le n^i$$; slo by ukazat i presneji pres odhad poctu konfiguraci: $$\text{pocet konfiguraci} \le |Q| \times |\Sigma| \times \log_2 n$$, coz projdem nejhur v case $$2^{c' \times \log_2 n}$$.

b := array [0..B] of Bool; // vyznam "uz jsme na vaze [index]"
b[0] := True;
b[zbytek] := false;

for a in A:
  for i := B to 0:
    if i + v(a) <= B && b[i]:
      b[ i + v(a)] := true;
  if b[B]:
    return Nalezeno;
return Nelze

To jiste probehne v O(nB), jiste $$B <= n^2$$ -> je to v O(n^3). Je to korektni -- kazdou vec pouzijeme nejvys jednou, pokud dojdem na pozadovanou vahu, vrati OK, pokud nedojdem umre.

5. Po cca. hodinovem premysleni :( jsem to dokazal uplnost za tri minuty prevodem z HK (+diskuse, ze je to z NP) -- chci ukazat, ze v G=(V,E) je HK <=> G1, G2 maji izomorfni podgraf. Polozim tedy G1 = G, G2 = kruznice nad |V| vrcholy. Tecka :).

Opet Kucerova poznamka, kterou jiz najdete ve foru ze vcerejska. Navic pry byl dnes stejny zapoctovy test jako vcera.

Doplním řešení úlohy č. 2:

Stačí si definici té množiny přepsat jako: $$S=\{e, (\exists p)(prime(p) \land \varphi_e(p)\downarrow)\}=\{e, (\exists p)(\exists s)(prime(p) \land \varphi_{e,s}(p)\downarrow)\}$$.

Platí, že S je rekurzivně spočetná právě tehdy, když ex. PRP $$P(e, p, s)$$ takový, že $$S=\{e, (\exists p)(\exists s)P(e, p, s)\}$$. Stačí tedy říct (nemuselo se to dokazovat), že $$P(e, p, s)=(prime(p) \land \varphi_{e,s}(p)\downarrow)$$ je PRP (první se dá odvodit a to druhé plyne z definice).

Ještě k úloze č. 4:

Pokud se někomu (jako třeba mně) nechtělo vymýšlet s algoritmem, stačilo ukázat, že se dá úloha polynomiálně převést na Batoh(s, c, B) (s(a):=v(a), c(a):=v(a)) a že úloha má řešení právě tehdy, když Batoh vrátí předměty o ceně přesně B. Jelikož Batoh má složitost $$O(nV \log_2(B+V))$$ a jelikož $$B\le V\le n^2$$, pak celá úloha má složitost $$O(n^3 \log n)$$.

jkt wrote:K tomu rovnou reseni:

1. Rovnou z Riceovy vety (snad se ani nemuselo ukazovat, ze to neni trivialni trida funkci).

Jo, to říkal Kučera po zkoušce a stejně nevím jak. Bylo mi to jasné i na zkoušce, že tam bude něco na Rice'ovu větu a vycházelo to jedině na tohle, ale stejně - "ani obraz ani zvuk" :-/

jkt wrote:3) Snadno, viz odhad, ze TS v case $$n^i$$ popise max. $$n^i$$ pasky, takze $$\rightarrow DSPACE(n^i) \subseteq DTIME(n^i)$$ a zaroven $$\exists i \in \mathbb{N}: \log_2 n \le n^i$$;

Tak přesně tohle jsem napsal i já, ale nebylo to dobře, podle lemmatu 12.2 je to přesně naopak, tedy $DTIME(f(n)) \subseteq DSPACE(f(n))$

jkt wrote:slo by ukazat i presneji pres odhad poctu konfiguraci: $$\text{pocet konfiguraci} \le |Q| \times |\Sigma| \times \log_2 n$$, coz projdem nejhur v case $$2^{c' \times \log_2 n}$$.

To bude asi lepší přístup ;-)

jkt wrote: 4)

b := array [0..B] of Bool; // vyznam "uz jsme na vaze [index]"
b[0] := True;
b[zbytek] := false;

for a in A:
  for i := B to 0:
    if i + v(a) <= B && b[i]:
      b[ i + v(a)] := true;
  if b[B]:
    return Nalezeno;
return Nelze

To jiste probehne v O(nB), jiste $$B <= n^2$$ -> je to v O(n^3). Je to korektni -- kazdou vec pouzijeme nejvys jednou, pokud dojdem na pozadovanou vahu, vrati OK, pokud nedojdem umre.

Wow, tak toto je geniálne a mňa to nenapadlo, potom som sa do toho zaplietol a už som to nedal...

jkt wrote: 5) Po cca. hodinovem premysleni :( jsem to dokazal uplnost za tri minuty prevodem z HK (+diskuse, ze je to z NP) -- chci ukazat, ze v G=(V,E) je HK <=> G1, G2 maji izomorfni podgraf. Polozim tedy G1 = G, G2 = kruznice nad |V| vrcholy. Tecka :).

Aké jednoduché ;-)