Денис Тугарёв
Реализация булевых функций на непересекающихся множествах переменных
Будут рассмотрены основные результаты статьи Wofgang J.Paul "Realizing boolean function on disjoint sets of variables" 1975. А именно доказательства следующих утверждений: для любого $\varepsilon > 0$ существует функция произвольной схемной сложности $f: \left\lbrace 0,1\right\rbrace^n \rightarrow \left\lbrace 0,1\right\rbrace^n$ такая, что $C(f \times f) \leqslant (1 + \varepsilon)C(f)$; для любого $\varepsilon > 0$ существует функция произвольной схемной сложности $g: \left\lbrace 0,1\right\rbrace^n \rightarrow \left\lbrace 0,1\right\rbrace$ такая, что $C(v\circ(g \times g)) \leqslant (1 + \varepsilon)C(g)$. Где $C(f), C(g)$ -- схемные сложности соответствующих булевых функций, $(f \times g)(x,y) = (f(x),g(y))$, $(f\circ g)(x) = f(g(x))$, $v:\left\lbrace 0,1 \right\rbrace^2 \rightarrow \left\lbrace 0,1 \right\rbrace$ и обозначает логическое OR.
