О средней монотонной сложности монотонных булевых функций
Дискретная математика · 2026 · 38 (2) · 149-160
DOI: 10.4213/dm1923 ↗Kurz gefasst
Fachartikel in der Zeitschrift Дискретная математика, online erschienen am 29.05.2026. Verfasst von Aleksandr Viktorovich Chashkin. Die Arbeit nennt 16 Literaturangaben. Gefördert von: Ministry of Science and Higher Education of the Russian Federation.
Abstract (Originalsprache)
Рассматривается средняя сложность вычисления монотонных булевых функций неветвящимися программами с условной остановкой в двух монотонных базисах. Для этих базисов найдены порядки соответствующих функций Шеннона для множества всех монотонных булевых функций. Показано, что существуют функции, для которых средние сложности в таких базисах, а также в полном базисе отличаются в экспоненциальное, относительно количества их переменных, число раз.
Förderung
- Ministry of Science and Higher Education of the Russian Federation
Zitieren
APA
Chashkin, A. V. (2026). О средней монотонной сложности монотонных булевых функций. Дискретная математика, 38(2), 149-160. https://doi.org/10.4213/dm1923
Vancouver
Chashkin AV. О средней монотонной сложности монотонных булевых функций. Дискретная математика. 2026;38(2):149-160. doi:10.4213/dm1923
BibTeX
@article{Chashkin2026,
author = {Chashkin, Aleksandr Viktorovich},
title = {О средней монотонной сложности монотонных булевых функций},
journal = {Дискретная математика},
year = {2026},
volume = {38},
number = {2},
pages = {149--160},
doi = {10.4213/dm1923}
}
EUVIMED