Инвариантный класс Q⊆P₂ замкнут относительно трёх операций: добавления и удаления фиктивных переменных, переименования переменных без их отождествления и подстановки констант вместо части переменных. Именно такие классы используются С. В. Яблонским для формализации неизбежности перебора при поиске функций с максимально сложной схемной
Последовательность f₁,f₂,… называется сложной, если в ней встречаются функции максимальной схемной сложности для сколь угодно больших чисел переменных. Теорема Яблонского утверждает: любой правильный алгоритм, строящий сложную последовательность, строит всё множество \(P_{2}\). Это результат о невозможности элиминации полного перебора в данной модели, а не утверждение об
Что важно запомнить
- Инвариантность означает замкнутость относительно фиктивных переменных, переименования без отождествления и подстановки
- Сложная функция \(f_n\) удовлетворяет \(L(f_n)=L(n)\).
- Сложная последовательность должна содержать такие функции для сколь угодно больших n, но не обязана состоять из максимальных функций при каждом
- Правильный алгоритм строит все функции минимального инвариантного класса, содержащего построенную последовательность.
- Теорема 2.6 Яблонского: правильный алгоритм, строящий сложную последовательность, строит всё
- Содержательный вывод — в этой постановке полный перебор всех ФАЛ устранить нельзя.
Инвариантные классы
Класс Q⊆P₂ называется инвариантным, если вместе с каждой f он содержит функции, получаемые добавлением или удалением фиктивных переменных, переименованием переменных без отождествления и фиксацией части переменных константами. Линейные и монотонные функции дают примеры инвариантных
Для инвариантного класса вводится характеристика σ, отражающая асимптотическую мощность Q(n). Если Q отличается от всего P₂, то σ<1. Результат Лупанова, используемый в доказательстве Яблонского, показывает, что функции такого собственного инвариантного класса имеют максимальную сложность не более \(\sigma\cdot 2^n/n\) в главном
Сложная последовательность
Функция \(f_n\) называется сложной, если \(L(f_n)=L(n)\), то есть достигает функции Шеннона СФЭ. Последовательность f₁(x₁), f₂(x₁,x₂), … называется сложной, если для любого N найдётся n≥N, при котором \(f_n\) сложна. Следовательно, максимальные по сложности функции должны встречаться бесконечно часто, но не обязательно при каждом
Правильный алгоритм и теорема Яблонского
Алгоритм, строящий бесконечную последовательность ФАЛ, называется правильным, если вместе с ней он строит все функции минимального инвариантного класса, содержащего эту последовательность. Теорема 2.6 Яблонского утверждает: любой правильный алгоритм, строящий сложную последовательность, строит всё \(P_{2}\)
Если бы построенная сложная последовательность лежала в собственном инвариантном \(Q_\sigma\), то σ<1 и для достаточно больших n сложность всех функций этого класса была бы асимптотически меньше \(2^n/n\). Это противоречит наличию в последовательности сколь угодно больших максимальных функций. Поэтому минимальный инвариантный класс сложной последовательности — всё P₂.
Смысл результата
Теорема формализует невозможность элиминации перебора всех булевых функций при построении сложной последовательности правильным алгоритмом. Она не говорит, что любой практический алгоритм минимизации конкретной схемы обязан буквально перечислять P₂, и не является утверждением об NP-полноте. Эти вопросы в пособии рассматриваются
Пример простыми словами
Представьте алгоритм, который строит сложную последовательность и затем «правильно» замыкает её относительно разрешённых операций. Вместе с найденными функциями он обязан получить их переименования, подстановки констант и варианты с фиктивными переменными. Если бы получившийся минимальный инвариантный класс был собственным \(Q_\sigma\) с \(\sigma<1\), то для достаточно больших \(n\) в нём не могло бы оставаться функций максимальной сложности \(L(n)\). Поэтому минимальный инвариантный класс сложной последовательности должен быть всем \(P_2\).
Частые ошибки
- Понимать инвариантный класс как класс, замкнутый относительно произвольной суперпозиции. В данном результате используется другой набор трёх операций.
- Считать, что сложная последовательность обязана содержать максимальную функцию при каждом n. Достаточно сколь угодно больших n.
- Обобщать теорему до утверждения, что любой алгоритм минимального синтеза всегда перебирает всё P₂. Результат относится к правильным алгоритмам и сложным последовательностям.
- Смешивать результат Яблонского с NP-полнотой. В пособии это отдельные разделы и разные подходы к алгоритмической сложности.
