Для любого ФПБ W(омега), число логических элементов необходимых для реализации произвольных функций от n k -значных переменных:, ,, где — константа, зависящая от выбора базиса (от n она не зависит), k – значность функции и независимых

переменных причем для любого e>0 доля функции f, для которой стремится к 0 с ростом n, т.е. с ростом числа переменных все функции реализуются со сложностью, близкой к верхней границе.

Чем больше входов в КА, то чтобы мы не делали, мы получим такое же число выходов.

Оценка сложности программы, необходимой для реализации произвольной обработки данных на операционном автомате, реализующий функционально-полный набор операций (команд), описывается тем же асимптотическим выражением, что и в теореме Шенонна-Лупанова, где К определяется из разрядности операционного автомата; n-объем обрабатываемых входных данных. В этом случае — сложность программы..