EUVIMEDEUVIMED entdecken
Crossref

О средней монотонной сложности монотонных булевых функций

Aleksandr Viktorovich Chashkin

Дискретная математика · 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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →