Асимптотически оптимальный по сложности синтез булевых схем с линейной динамической активностью для произвольных булевых функций
Получена: 08.11.2026 Доработана: 09.11.2026 Принята: 09.11.2026
Опубликована: 2026 год, том 30, выпуск 4, С. 212–215
Аннотация
Рассматривается задача синтеза схем из функциональных элементов (СФЭ) с одновременными ограничениями на взвешенную сложность и динамическую активность — наибольшее число элементов, значения которых различаются на двух входных наборах. Показано, что для любого конечного полного базиса \(\mathcal B\), принадлежащего объединению двух специальных классов таких базисов, и для любой булевой функции \(f(x_1,\ldots ,x_n)\) можно построить такую реализующую её СФЭ \(\Sigma _f\) в базисе \(\mathcal B\), сложность \(L(\Sigma _f)\) и динамическая активность \(C(\Sigma _f)\) которой при \(n=1,2,\ldots\) удовлетворяют неравенствам: \[\begin {gathered} L(\Sigma _f)\le \rho (\mathcal B)\frac {2^n}{n} \left (1+\frac {6\log _2 n}{n}+O\!\left (\frac 1n\right )\right ),\quad C(\Sigma _f)=O(n), \end {gathered}\] где \(\rho (\mathcal B)\) — наименьший приведённый вес элементов базиса. Заметим, что первая из этих оценок асимптотически совпадает с соответствующей функцией Шеннона, а вторая даёт линейную верхнюю границу.
Ключевые слова: булевы схемы, взвешенная сложность, динамическая активность, функция Шеннона, оптимизация схем по двум параметрам.
BibTeX
@article{IS-Dai-Lozhkin2026,
author = {Дай, Юэ and Ложкин, Сергей Андреевич},
title = {{Асимптотически оптимальный по сложности синтез булевых схем с линейной динамической активностью для произвольных булевых функций}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2026},
volume = {30},
number = {4},
pages = {212--215},
}
AMSBIB
\RBibitem{IS-Dai-Lozhkin2026}
\by Ю.~Дай, С.\,А.~Ложкин
\paper Асимптотически оптимальный по сложности синтез булевых схем с линейной динамической активностью для произвольных булевых функций
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 4
\pages 212--215
EN