Асимптотически оптимальный по сложности синтез булевых схем с линейной динамической активностью для произвольных булевых функций

Аннотация

Рассматривается задача синтеза схем из функциональных элементов (СФЭ) с одновременными ограничениями на взвешенную сложность и динамическую активность — наибольшее число элементов, значения которых различаются на двух входных наборах. Показано, что для любого конечного полного базиса \(\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
Опубликовано на условиях лицензии Creative Commons Attribution 4.0 International (CC BY 4.0)

← К номеру журнала

× Issue cover