Abychom mohli alespoò adresovat vstup, musí být $w\ge\log N$,
kde $N$ je celková velikost vstupu.
Jeliko¾ aritmetiku s~$\O(1)$-násobnou pøesností lze simulovat s~konstantním
-zpomalením, mù¾eme pøedpokládat, ¾e $w=\Omega(\log n)$, tedy ¾e lze pøímo pracovat
+zpomalením, mù¾eme pøedpokládat, ¾e $w=\Omega(\log N)$, tedy ¾e lze pøímo pracovat
s~èísly polynomiálnì velkými vzhledem k~$N$. Je¹tì bychom si mìli ujasnit,
jakou mno¾inu operací povolíme:
}}$$
My se pøidr¾íme ekvivalentní, ale jednodu¹¹í definice podle Erika Demaine~\cite{demaine}.
-\s{Definice:} VEBT($U$) pro universum velikosti $U$ (BÚNO $U=2^{2^k}$)
+\s{Definice:} VEBT($U$) pro universum velikosti $U$ (BÚNO $U=2^k=2^{2^\ell}$)
obsahuje:
\itemize\ibull
ale je definováno, ¾e neinicializovanou buòku mù¾eme pøeèíst a dostaneme
nìjakou korektní, i kdy¾ libovolnou, hodnotu. Tehdy nám pomù¾e:
-{\narrower
+%{\narrower\medskip
\s{Vìta:} Buï $P$ program pro Word-RAM s~nulami inicializovanou
pamìtí, bì¾ící v èase $T(n)$. Pak existuje program~$P'$ pro Word-RAM
v~tém¾e èase udr¾ovat.
\qed
-}
+%\medskip}
\s{\uv{Minové pole}:} Neinicializované buòky není ani dovoleno èíst.
V~tomto pøípadì nejsme schopni deterministické redukce, ale alespoò
Libovolný $n$-slo¾kový vektor, jeho¾ slo¾ky jsou $b$-bitová èísla
($n(b+1)\le w$), zakódujeme poskládáním jednotlivých slo¾ek vektoru za~sebe,
prolo¾enì nulovými bity:
+
+\nobreak
\alik{\0 x_{n-1} \0 x_{n-2} \9\9\9 \0 x_1\0 x_0 \cr}
\>S~vektory budeme provádìt následující operace: (latinkou znaèíme vektory,
Nejdøíve èíslo~$\alpha$ replikujeme, pak andujeme vhodnou bitovou maskou,
aby v~$i$-té slo¾ce zùstal pouze $i$-tý bit a ostatní se vynulovaly,
-a pak provedeme $\<Cmp>$ s~vektorem reprezentovaným touté¾ bitovou maskou.
+a pak provedeme $\<Cmp>$ s~vektorem samých nul.
\:$\<Unpack>_\varphi(\alpha)$ -- podobnì jako pøedchozí operace, ale bity je¹tì
prohází podle nìjaké pevné funkce $\varphi$:
Staèí zvolit bitovou masku, která v~$i$-té slo¾ce ponechá právì $\varphi(i)$-tý bit.
+\finalfix{\goodbreak}
+
\:$\<Pack>(x)$ -- dostane vektor nul a jednièek a vytvoøí èíslo, jeho¾ bity
jsou právì slo¾ky vektoru (jinými slovy ¹krtne nuly mezi bity):
\>Poslední dvì operace doká¾eme spoèítat i v~lineárním prostoru, napøíklad
pro \<MSB> takto: Rozdìlíme èíslo na bloky velikosti $\lfloor\sqrt{w}\rfloor$.
-Pak pro ka¾dý blok zjistíme, zda v nìm je aspoò jedna jednièka, zavoláním
+Pak pro ka¾dý blok zjistíme, zda v~nìm je aspoò jedna jednièka, zavoláním
$\<Cmp>(0,x)$. Pomocí \<Pack> z~toho dostaneme slovo~$y$ odmocninové
délky, jeho¾ bity indikují neprázdné bloky. Na~toto èíslo zavoláme pøedchozí
kvadratické \<MSB> a zjistíme index nejvy¹¹ího neprázdného bloku.