Аннотация:
Рассматривается средняя сложность вычисления монотонных булевых функций неветвящимися программами с условной остановкой в базисе из всех не более чем двухместных булевых функций. При $n\to\infty$ для множества всех $n$-местных монотонных булевых функций установлены новые верхние и нижние оценки средней сложности шенноновского типа.
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, проект 14-01-00598.
Ключевые слова:монотонные булевы функции, средняя сложность.
Полный текст:
PDF файл (533 kB)