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