Мощностный метод Шеннона получает нижние оценки сложности сравнением двух количеств: числа всех n-местных ФАЛ, равного \(2^{2^n}\), и числа попарно неэквивалентных схем ограниченной сложности. Если схем сложности не более L недостаточно, чтобы реализовать все функции, то существует функция сложности больше L. Если таких схем хватает лишь на малую долю функций, та же нижняя оценка справедлива для почти всех
Для основных моделей отсюда следуют асимптотические границы \(L^C(n)\ge (1-o(1))2^n/n\), \(L^K(n)\ge (1-o(1))2^n/n\), \(L^\Phi (n)\ge (1-o(1))2^n/\log n\) и \(L^\pi (n)\ge (1-o(1))2^n/\log n\). Для глубины формул получается D(n)>n−log log
Что важно запомнить
- Всего существует \(2^{2^n}\) булевых функций от n переменных.
- Подсчёт схем ограниченной сложности даёт верхнюю границу числа функций, которые эти схемы могут реализовать.
- Если число доступных функциональных классов схем меньше \(2^{2^n}\), часть функций неизбежно требует большей
- Для СФЭ и КС нижний порядок равен \(2^n/n\), а для формул и π-схем — \(2^n/\log\)
- Такие оценки можно усилить до утверждений о почти всех ФАЛ, если схем малой сложности реализуют исчезающе малую долю функций.
- Метод обычно не указывает конкретную функцию, достигающую нижней границы.
Идея мощностного метода
Пусть U(L,n) — множество схем выбранного класса, реализующих одну n-местную ФАЛ и имеющих сложность не более L. Каждая схема задаёт не более одной функции. Поэтому число функций, реализуемых схемами из U(L,n), не превосходит числа классов таких схем. Если эта величина меньше \(2^{2^n}\), то схемы сложности ≤L не могут покрыть всё P₂(n). Следовательно, функция Шеннона выбранного класса больше
Переход от существования к почти всем функциям
Если число функций, реализуемых схемами сложности ≤L, не превосходит \(\delta\cdot 2^{2^n}\), то не менее доли 1−δ всех ФАЛ имеют сложность больше L. Именно так мощностный метод одновременно даёт нижние оценки функции Шеннона и типичной сложности почти всех
Основные следствия
Используя перечислительные оценки числа формул, СФЭ, контактных и π-схем, получают \(L^C(n)\ge (1-o(1))2^n/n\) и \(L^K(n)\ge (1-o(1))2^n/n\). Для формул и π-схем знаменатель меняется на log n: \(L^\Phi (n)\ge (1-o(1))2^n/\log n\) и \(L^\pi (n)\ge (1-o(1))2^n/\log n\). Для глубины формул получается D(n)>n−log log
Тот же принцип переносится на специальный класс Q(n): вместо мощности P₂(n) используют |Q(n)|. Поэтому мощностный метод особенно полезен для функций Шеннона целых классов, но сам по себе обычно не является способом доказать трудность заранее заданной индивидуальной функции.
Пример простыми словами
Если некоторый класс схем сложности не более L способен реализовать максимум один миллион различных функций, а рассматриваемых функций два миллиона, то хотя бы миллион функций требуют сложности больше L. Мощностный метод делает то же самое в огромном масштабе, сравнивая число схем с \(2^{2^n}\) возможными ФАЛ.
Частые ошибки
- Считать мощностную нижнюю оценку конструктивной. Она доказывает существование трудных функций, но обычно не называет их.
- Путать функцию Шеннона с типичной сложностью. Для максимума достаточно одной трудной функции, а утверждение о почти всех требует отдельной оценки доли.
- Менять местами знаменатели n и log n. Для СФЭ и КС возникает n, для формул и π-схем — log n.
- Использовать мощностную оценку класса как доказательство сложности произвольно выбранной конкретной ФАЛ.
