Шаг 1. Зафиксировать модель
Запись L(f) имеет смысл только относительно конкретного класса схем и функционала. Например, число функциональных элементов и число контактов — разные ресурсы. Поэтому сначала выбирают U и L, а затем формулируют обе оценки в одной и той же модели.1
Шаг 2. Построить верхнюю оценку
Любая явная схема даёт верхнюю границу. Универсальные способы включают синтез по СДНФ, контактное дерево, каскадный метод, функциональное разложение, суперпозицию, методы Шеннона и Лупанова. Для специальной функции выгоднее использовать её собственные свойства: симметрию, линейность, повторяющиеся кофакторы или общие подфункции нескольких выходов.
Шаг 3. Доказать нижнюю оценку
Простейшие нижние границы выводятся из существенной зависимости и необходимости определённых элементов или контактов. Более сильные индивидуальные оценки могут использовать ограничения функции: если после фиксации части входов получается уже известная трудная функция, исходная схема не может быть проще её ограничения. Для функций Шеннона и больших классов применяется мощностный метод. Важно не переносить такой неконструктивный результат автоматически на заранее выбранную f.1
Системы функций
Для \(F=(f_{1},\ldots,f_m)\) при функционале L выполняется \(\max_i L(f_i)\le L(F)\le \sum_i L(f_i)\). Левая часть обязательна, потому что общая схема должна реализовать каждую компоненту. Правая часть получается объединением минимальных схем компонентов. Но общая схема часто может быть меньше суммы за счёт совместного использования подвычислений.
Когда сложность известна точно
Если построена схема сложности U и доказано, что любая схема имеет сложность не меньше U, получаем равенство. Например, для \(f=x_{1}\vee \ldots \vee x_n\) контактная реализация из n параллельных контактов даёт \(L^K(f)\le n\). Существенная зависимость от всех n переменных даёт \(L^K(f)\ge n\). Следовательно, \(L^K(f)=n\).