Для специального класса Q(n) вводят собственную функцию Шеннона: максимум сложности не по всему P₂(n), а только по f∈Q(n). Нижнюю оценку можно получить мощностным методом из |Q(n)|, а верхнюю — конструкцией, использующей конкретную структуру класса. Поэтому структурные ограничения класса могут уменьшить его максимальную схемную сложность по сравнению со всем
Характерный пример — ФАЛ, симметричные по первым двум переменным. Для них два из четырёх кофакторов совпадают, поэтому требуется реализовать только три независимых кофактора. В курсе получена асимптотика \(L^C(Q(n))\sim L^K(Q(n))\sim (3/4)\cdot 2^n/n\)
Что важно запомнить
- Для Q(n) рассматривается \(L^U(Q(n))=\max_{f\in Q(n)}L^U(f)\), а не максимум по всем P₂(n).
- Мощность |Q(n)| даёт основу для нижней мощностной оценки сложности
- Верхняя оценка должна использовать конкретное ограничение класса: симметрию, повторение кофакторов, специальную декомпозицию или другую структуру.
- Для функций, симметричных по x₁ и x₂, выполняется \(f_{01}=f_{10}\), поэтому остаются три независимых кофактора вместо
- Для этого класса
- Для индивидуальной функции точную или асимптотически точную сложность получают, когда явная верхняя конструкция совпадает с отдельной нижней оценкой.
Функция Шеннона специального класса
Пусть Q(n)⊆P₂(n). Для выбранной модели схем рассматривают \(L^U(Q(n))=\max_{f\in Q(n)}L^U(f)\). Если класс существенно меньше P₂(n), подсчёт схем сравнивают уже с |Q(n)|. Так получают мощностную нижнюю оценку именно для Q. Затем нужно построить верхнюю реализацию, которая использует определяющее свойство
Пример: симметрия по двум переменным
Пусть Q состоит из функций, симметричных по первым двум переменным. Разложение по x₁,x₂ содержит кофакторы f₀₀, f₀₁, f₁₀, f₁₁, но симметрия даёт \(f_{01}=f_{10}\). Значит, вместо четырёх независимых функций от остальных n−2 переменных нужно асимптотически оптимально реализовать только три. Отсюда строится верхняя оценка с коэффициентом 3/4, а мощностная оценка даёт такой же главный член. В результате
\(L^C(Q(n))\sim L^K(Q(n))\sim (3/4)\cdot 2^n/n\).
Индивидуальные функции и системы
Для конкретной ФАЛ общий мощностный аргумент класса обычно недостаточен: он не показывает, что именно выбранная функция трудна. Верхнюю оценку получают явной схемой, используя ДНФ, каскад, разложение, симметрию или другую структуру. Нижнюю оценку доказывают отдельно через существенные переменные, полярности, ограничения, специальные инварианты или иные свойства функции. Совпадение двух оценок доказывает точную сложность. Для структурированных систем функций дополнительно выгодно совместное использование общих
Пример простыми словами
Разложение по \(x_1,x_2\) даёт четыре кофактора \(f_{00},f_{01},f_{10},f_{11}\). Для функции, симметричной по первым двум переменным, \(f_{01}=f_{10}\), поэтому остаются только три независимых кофактора от остальных \(n-2\) переменных вместо четырёх. Именно это уменьшение числа независимых частей объясняет коэффициент \(3/4\) в главном члене сложности данного специального класса.
Частые ошибки
- Применять асимптотику для всего P₂(n) как заведомо точную для специального подкласса.
- Считать мощностную нижнюю оценку класса доказательством трудности любой конкретной функции из него.
- Игнорировать повторяющиеся кофакторы и другие структурные ограничения, из-за которых специальный класс может быть проще.
- Полагать, что любая симметрия автоматически даёт коэффициент 3/4. Этот коэффициент относится к конкретному классу симметрии по первым двум переменным.
