Теорема: (основная теорема оценки трудоемкости синтеза)

Существует метод синтеза формального представления дискретной функции при котором количество не нулевых коэффициентов разложения M(m) и число операций L(m) необходимых для ее вычисления, удовлетворяют следующим асимптотическим оценкам. Устремим длину характеристического вектора .

– число операций, необходимых для вычисления функций.

– объем памяти, необходимый для хранения коэффициентов.

Где m – число переменных, на которые разбивается аргумент функции.

n~log_k(m)

Замечание:

1. При выводе теоремы использовалась произвольная функционально полная система операции, состоящая из всех известных унарных и бинарных операций.

2. Почти все функции не имеют эффективной программной или аппаратной реализации.

3. Необходимо использовать архитектурное проектирование вычислительных средств с использованием архитектурных принципов заключающихся в декомпозиции обработки данных на части, а так же представление этой декомпозиции в виде блок-схемы. Декомпозиция завершается когда полученные блоки представляют элементы которые могут быть реализованы на практике.