Простейшие нижние оценки выводятся из обязательных структурных ресурсов схемы. Если ФАЛ \(f(x_{1},\ldots,x_n)\) существенно зависит от всех n переменных, то для СФЭ \(L^C(f)\ge n-1\), а для контактных схем \(L^K(f)\ge n\)
Если при этом f немонотонна, для СФЭ требуется хотя бы один элемент отрицания и оценка усиливается до \(L^C(f)\ge n\). Если k переменных функции не являются ни монотонными, ни инмонотонными, контактная схема должна содержать для каждой из них оба типа контактов \(x_i\) и \(\neg x_i\), поэтому \(L^K(f)\ge n+k\)
Что важно запомнить
- Существенная зависимость от n переменных даёт \(L^C(f)\ge n-1\) и
- Если f существенно зависит от всех n переменных и немонотонна, то \(L^C(f)\ge n\).
- При тех же условиях, если k переменных ни монотонны, ни инмонотонны, то \(L^K(f)\ge n+k\).
- Для функции чётности \(\ell_n\) отсюда следуют \(L^C(\ell_n)\ge n\) и
- Нижняя оценка сама по себе не даёт точную сложность. Равенство нужно подтвердить конструкцией той же сложности.
СФЭ: оценка через число используемых входов
Пусть минимальная СФЭ \(\Sigma_f\) реализует f, существенно зависящую от \(x_{1},\ldots,x_n\). Тогда ранг схемы \(R(\Sigma_f)\), то есть число дуг, выходящих из входных вершин, не меньше n. Для приведённой одно-выходной СФЭ выполняется \(R(\Sigma)\)\(\le L_{\wedge,\vee}(\Sigma)+1\). Отсюда
\(L^C(f)\ge n-1\).
Если f немонотонна, в схеме необходим хотя бы один элемент ¬. Тогда к n−1 элементам ∧/∨ добавляется отрицание и получается \(L^C(f)\ge n\).
Контактные схемы: оценка через пометки контактов
Если f существенно зависит от \(x_i\), в любой реализующей КС должен встретиться контакт, помеченный \(x_i\) или \(\neg x_i\). Иначе изменение \(x_i\) не могло бы изменить проводимость. Поэтому для n существенных переменных требуется не менее n контактов:
\(L^K(f)\ge n\).
Если переменная \(x_i\) не является ни монотонной, ни инмонотонной, одной полярности контакта недостаточно: в схеме должны встречаться и \(x_i\), и \(\neg x_i\). Если таких переменных k, получаем \(L^K(f)\ge n+k\)
Когда нижняя оценка доказывает минимальность
Нижняя оценка становится точным результатом, если есть схема с такой же сложностью. Например, для элементарной дизъюнкции \(x_{1}\vee \ldots \vee x_n\) каноническая π-схема имеет n контактов. Нижняя оценка \(L^K\ge n\) совпадает с конструкцией и тем самым доказывает её минимальность.
Пример простыми словами
Для функции чётности \(\ell_n\) каждая переменная существенно влияет на результат и не является ни монотонной, ни инмонотонной. Поэтому для КС k=n и простейшая оценка сразу даёт \(L^K(\ell_n)\ge 2n\). Это пример того, как одно качественное свойство функции превращается в количественную границу сложности.
Частые ошибки
- Использовать \(L^C(f)\ge n-1\) для функции, которая фактически зависит от меньшего числа переменных.
- Делать вывод о минимальности только из нижней оценки. Нужна ещё реализующая схема той же сложности.
- Путать немонотонность функции в целом и переменную, которая не является ни монотонной, ни инмонотонной. Для оценки n+k учитываются именно такие переменные.
