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

Рассматриваются схемы из ненадежных функциональных элементов. Предполагается, что все элементы схемы ошибаются независимо друг от друга с вероятностью $\varepsilon$. Под избыточностью самокорректирующейся схемы, реализующей некоторую функцию, понимается отношение числа элементов – сложности самокорректирующейся схемы из ненадежных элементов к сложности схемы из надежных элементов, реализующей ту же функцию. Показано, что для некоторых функций избыточность реализующих их самокорректирующихся схем растет не медленнее, чем логарифм сложности схемы из надежных элементов.