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