RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 1987, том 26, номер 1, страницы 3–26 (Mi al1967)

Эта публикация цитируется в 6 статьях

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

А. Е. Андреев


Аннотация: Рассматривается задача получения нижних оценок для сложности реализации индивидуальных монотонных функций схемами из функциональных элементов в монотонных базисах. Основным результатом является общая оценка монотонной сложности булевой функции через некоторые ее комбинаторные характеристики. Приведен пример последовательности монотонных функции, для которых полученная оценка имеет рост $2^{n^{1/3-o(1)}}$, где $n$ — число переменных.

УДК: 519.95

Поступило: 19.02.1986



Реферативные базы данных:


© МИАН, 2024