|
Алгебра и логика, 1987, том 26, номер 1, страницы 3–26
(Mi al1967)
|
|
|
|
Эта публикация цитируется в 6 научных статьях (всего в 6 статьях)
Об одном методе получения эффективных нижних оценок монотонной сложности
А. Е. Андреев
Аннотация:
Рассматривается задача получения нижних оценок для сложности реализации индивидуальных монотонных функций схемами из функциональных элементов в монотонных базисах. Основным результатом является общая оценка монотонной сложности булевой функции через некоторые ее комбинаторные характеристики. Приведен пример последовательности монотонных функции, для которых полученная оценка имеет рост $2^{n^{1/3-o(1)}}$, где $n$ — число переменных.
Поступило: 19.02.1986
Образец цитирования:
А. Е. Андреев, “Об одном методе получения эффективных нижних оценок монотонной сложности”, Алгебра и логика, 26:1 (1987), 3–26
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al1967 https://www.mathnet.ru/rus/al/v26/i1/p3
|
Статистика просмотров: |
Страница аннотации: | 227 | PDF полного текста: | 49 | Список литературы: | 1 |
|