Santa Claus — 2022-11-29 00:26 (37 days ago) — edit — reply
Řekněme, že daný obvod umíme postavit pro vstup délky n. Pak ho ale umíme postavit i pro vstup délky $\frac{n}2$, a sice takto:
Vstup délky $2n$ rozdělíme jednoduše po bitech na horní (h) a dolní (d) polovinu. Podíváme se na obě poloviny zvlášť:
Triviálně platí
$y > x \iff y_h > x_h$ nebo $(y_h \nless x_h$ a $y_d > x_d)$
Pro $\nless$ můžeme použít naše hradlo. Celý tento výrok je složen z AND, OR a $<$, hradla, která máme k dispozici.
Hloubku tím zvětšíme o konstantu, pouze jedno AND hradlo a výstup přivedeme do OR hradla. $h(n + 1) = h(n) + 2$, $2 \in O(\log(n))$, $h(n) \in O(\log(n))$ plyne z předpokladu.
Nyní ale musíme dokončit naše induktivní hradlo pro případ $n = 1$. To je ale jednoduché, aby $a < b$, musí platit $a = 0, b = 1$. Ostatní kombinace nuly a jedničny dávají nepravdu. Jedna negace a jeden AND $AND(NOT(a),b)$, je hradlo hloubky 2.
Nakonec se hodí zmínit, že vstupy, které nelze rozdělovat napůl až do dosažení jedničky, můžeme jednoduše doplnit nulami zleva.