m-регулярное множество \(\delta\subseteq B^q\) имеет мощность \(2^m\) и содержит ровно один набор с каждым префиксом длины m. Поэтому оставшиеся q−m координат на δ однозначно задаются функциями первых m переменных. На подходящем регулярном разбиении специальные функции можно локально моделировать самими переменными
Эта техника позволяет перенести идею Лупанова на формулы, где нельзя свободно разветвлять промежуточные результаты. Для любой f∈P₂(n) существует формула со сложностью \(L(F_f)\le (2^n/\log n)\cdot (1+(2 \log \log n+O(1))/\log n)\). Отсюда \(L^\Phi (n)\sim 2^n/\log n\)
Что важно запомнить
- В m-регулярном \(\delta\subseteq B^q\) выполняются m<q, \(|\delta|=2^m\) и различны все префиксы длины
- На δ последние q−m координат являются функциями первых m координат.
- Регулярное разбиение строят так, чтобы функции из ДУМ на каждой компоненте совпадали с отдельными переменными или их локальными
- Это позволяет заменить дорогое повторение функций ДУМ в формуле более дешёвыми локальными переменными.
- Теорема 7.1 даёт
- Следствие: \(L^\Phi (n)\sim 2^n/\log n\).
Регулярные множества
Пусть m<q. Множество \(\delta\subseteq B^q\) называется m-регулярным, если \(|\delta|=2^m\) и все префиксы длины m у его наборов различны. Значит, каждому \(\beta\in B^m\) соответствует ровно один набор (β,γ)∈δ. Поэтому γ является значением некоторой системы из q−m булевых функций от β. И наоборот, такая система функций однозначно задаёт m-регулярное
Важно, что m-регулярное множество не обязано быть m-мерной гранью. Это граф системы функций над всеми m-битными префиксами.
Моделирование функций переменными
Специальное регулярное разбиение строится для системы функций из ДУМ так, чтобы на каждой компоненте разбиения эти функции совпадали с координатными переменными. Внутри компоненты сложная функция из универсального набора тем самым заменяется буквой, а произвольный кофактор превращается в относительно короткую дизъюнкцию таких
Почему это важно именно для формул
СФЭ может реализовать функцию из ДУМ один раз и разветвить её результат. Формула такого разветвления не допускает и обычно должна повторять подформулу в каждом месте использования. Регулярные разбиения обходят эту проблему локальным моделированием функций переменными. После оптимального выбора параметров теорема 7.1 даёт
\(L(F_f)\le (2^n/\log n)\cdot (1+(2 \log \log n+O(1))/\log n)\).
Совместно с мощностной нижней оценкой это приводит к асимптотике \(L^\Phi (n)\sim 2^n/\log n\).
Пример простыми словами
При q=3 и m=2 регулярное множество содержит четыре набора. Для каждого двухбитного префикса 00, 01, 10 и 11 в нём есть ровно один набор. Третья координата поэтому является некоторой функцией первых двух. На таком множестве эту функцию можно воспринимать просто как координатную переменную x₃.
Частые ошибки
- Считать m-регулярное множество обычной гранью куба. Его определяет уникальность продолжения каждого m-битного префикса.
- Путать регулярное разбиение с разбиением, использованным только для определения ДУМ. В §7 регулярность нужна для моделирования функций переменными.
- Переносить на формулы асимптотику \(2^n/n\), справедливую для СФЭ. Для формул главный знаменатель — log n.
- Забывать, что в формулах промежуточный результат нельзя свободно разветвлять, поэтому требуется отдельная техника устранения повторов.
