Существуют оптимальные по порядку числа элементов надежные схемы из ненадежных функциональных элементов

Пусть $\varphi_{\delta}^s(x_1,\dots,x_k)$ – булева функция, значение которой равно 0 на двоичных наборах с весом $0,1,\dots,]s-\delta k[$ и 1 на двоичных наборах с весом $]s+\delta k[,\dots,k-1,k$. На остальных наборах функция $\varphi_{\delta}^s(x_1,\dots,x_k)$ не определена. Показано, что существует метод синтеза, который, позволяет надежно реализовать в схеме из ненадежных элементов (с вероятностью ошибки $\varepsilon$ каждого элемента $\leq\varepsilon(\delta))$ любую функцию $\varphi_{\delta}^s(x_1,\dots,x_k)$ так, что число элементов полученной схемы не превосходит $c(\delta)k$, где $c(\delta)$ не зависит от $k$.