Нижняя оценка сложности булевых операторов
Abstract
В работе для явно заданного булева линейного $(n,o(n))$-оператора доказана нижняя оценка сложности $2n-o(n)$ при реализации логическими схемами над базисом всех двуместных булевых функций. На базе этого примера получены конструктивные нижние оценки: $5.1n-o(n)$ для булева $(n,n)$-оператора и ${4n-o(n)}$ для линейного булева $(n,n)$-оператора.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Coding theory and cryptography
Computability
Logic
AI Algorithms
Publication details
- Journal / source
- Дискретная математика
- Volume
- 38
- Issue
- 1
- Pages
- 95–106
- Publication date
- 1 January 2026
- Language
- RU