Korektury od Martina Jiricky.

[ads2.git] / 11-np / 11-np.tex

diff --git a/11-np/11-np.tex b/11-np/11-np.tex
index 171e51d8d3124a444e3cffe4c356e5ad5e7078e0..c81d9131215b89839daaf4f94d32e0eaa877f6cc 100644 (file)
--- a/11-np/11-np.tex
+++ b/11-np/11-np.tex
@@ -273,7 +273,7 @@ na~obvodov
 (chápeme jako posloupnost $x_1, x_2, \ldots, x_n$),
 spoèítáme velikost nápovìdy $g(n)$. Víme, ¾e kontrolní
 algoritmus~$K$ (který kontroluje, zda nápovìda je správnì) je v~P. Vyu¾ijeme
-pøedhozí lemma, abychom získali obvod, který pro konkrétní velikost vstupu
+pøedchozí lemma, abychom získali obvod, který pro konkrétní velikost vstupu
 $x$ poèítá to, co kontrolní algoritmus $K$. Na vstupu tohoto obvodu bude $x$
 (vstup problému $L$) a~nápovìda~$y$. Na výstupu nám øekne, jestli je nápovìda
 správná. Velikost vstupu tohoto obvodu bude tedy $p(g(n))$, co¾ je také polynom.
@@ -285,7 +285,8 @@ spr
 \>Pro libovolný problém z~NP tak doká¾eme sestrojit funkci, která pro ka¾dý vstup~$x$ v~polynomiálním èase vytvoøí obvod, který je splnitelný pravì tehdy, kdy¾ odpovìï tohoto problému na vstup $x$ má být \<true>. Tedy libovolný problém z~NP se dá
 v~polynomiálním èase pøevést na obvodový SAT.
 
-\>Obvodový SAT je v NP triviálnì - ??? staèí topologicky setøídit a pak brát hradla postupnì.???
+\>Obvodový SAT je v NP triviálnì -- staèí si nechat poradit vstup, sí»
+topologicky setøídit a v~tomto poøadí poèítat hodnoty hradel.
 \qed
 
 \s{Lemma:} Obvodový SAT se dá pøevést na 3-SAT.