Простейшие нижние оценки выводятся из обязательных структурных ресурсов схемы. Если ФАЛ f(x₁,…,x_n) существенно зависит от всех n переменных, то для СФЭ \(L^C(f)\ge n-1\), а для контактных схем \(L^K(f)\ge n\)
Если при этом f немонотонна, для СФЭ требуется хотя бы один элемент отрицания и оценка усиливается до \(L^C(f)\ge n\). Если k переменных функции не являются ни монотонными, ни инмонотонными, контактная схема должна содержать для каждой из них оба типа контактов x_i и ¬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\).
- Для функции чётности ℓ_n отсюда следуют L^C(ℓ_n)≥n и
- Нижняя оценка сама по себе не даёт точную сложность. Равенство нужно подтвердить конструкцией той же сложности.
СФЭ: оценка через число используемых входов
Пусть минимальная СФЭ Σ_f реализует f, существенно зависящую от x₁,…,x_n. Тогда ранг схемы R(Σ_f), то есть число дуг, выходящих из входных вершин, не меньше n. Для приведённой одно-выходной СФЭ выполняется \(R(\Sigma)\)≤L_{∧,∨}(Σ)+1. Отсюда
\(L^C(f)\ge n-1\).
Если f немонотонна, в схеме необходим хотя бы один элемент ¬. Тогда к n−1 элементам ∧/∨ добавляется отрицание и получается \(L^C(f)\ge n\).
Контактные схемы: оценка через пометки контактов
Если f существенно зависит от x_i, в любой реализующей КС должен встретиться контакт, помеченный x_i или ¬x_i. Иначе изменение x_i не могло бы изменить проводимость. Поэтому для n существенных переменных требуется не менее n контактов:
\(L^K(f)\ge n\).
Если переменная x_i не является ни монотонной, ни инмонотонной, одной полярности контакта недостаточно: в схеме должны встречаться и x_i, и ¬x_i. Если таких переменных k, получаем \(L^K(f)\ge n+k\)
Когда нижняя оценка доказывает минимальность
Нижняя оценка становится точным результатом, если есть схема с такой же сложностью. Например, для элементарной дизъюнкции x₁∨…∨x_n каноническая π-схема имеет n контактов. Нижняя оценка L^K≥n совпадает с конструкцией и тем самым доказывает её минимальность.
Пример простыми словами
Для функции чётности ℓ_n каждая переменная существенно влияет на результат и не является ни монотонной, ни инмонотонной. Поэтому для КС k=n и простейшая оценка сразу даёт L^K(ℓ_n)≥2n. Это пример того, как одно качественное свойство функции превращается в количественную границу сложности.
Частые ошибки
- Использовать \(L^C(f)\ge n-1\) для функции, которая фактически зависит от меньшего числа переменных.
- Делать вывод о минимальности только из нижней оценки. Нужна ещё реализующая схема той же сложности.
- Путать немонотонность функции в целом и переменную, которая не является ни монотонной, ни инмонотонной. Для оценки n+k учитываются именно такие переменные.
