Нижняя оценка сложности булевых операторов
Дискретная математика · 2026 · 38 (1) · 95-106
DOI: 10.4213/dm1903 ↗Kurz gefasst
Fachartikel in der Zeitschrift Дискретная математика, online erschienen am 01.03.2026. Verfasst von Igor Sergeevich Sergeev. Die Arbeit nennt 13 Literaturangaben.
Abstract (Originalsprache)
В работе для явно заданного булева линейного $(n,o(n))$-оператора доказана нижняя оценка сложности $2n-o(n)$ при реализации логическими схемами над базисом всех двуместных булевых функций. На базе этого примера получены конструктивные нижние оценки: $5.1n-o(n)$ для булева $(n,n)$-оператора и ${4n-o(n)}$ для линейного булева $(n,n)$-оператора.
Zitieren
APA
Sergeev, I. S. (2026). Нижняя оценка сложности булевых операторов. Дискретная математика, 38(1), 95-106. https://doi.org/10.4213/dm1903
Vancouver
Sergeev IS. Нижняя оценка сложности булевых операторов. Дискретная математика. 2026;38(1):95-106. doi:10.4213/dm1903
BibTeX
@article{Sergeev2026,
author = {Sergeev, Igor Sergeevich},
title = {Нижняя оценка сложности булевых операторов},
journal = {Дискретная математика},
year = {2026},
volume = {38},
number = {1},
pages = {95--106},
doi = {10.4213/dm1903}
}
EUVIMED