|
Математические заметки, 1985, том 37, выпуск 6, страницы 887–900
(Mi mzm5393)
|
|
|
|
Эта публикация цитируется в 47 научных статьях (всего в 47 статьях)
Нижние оценки монотонной сложности логического перманента
А. А. Разборов
Аннотация:
Логическим перманентом $f_m$ булевой матрицы $m\times m$ называется монотонная булева функция $\bigvee_{\sigma\in S_m}\&_{i=1}^mx_{i\sigma(i)}$. Монотонной сложностью $L_f^+$ монотонной булевой функции $f$ называется наименьшее число функциональных элементов И, ИЛИ, необходимое для ее реализации в виде функциональной схемы. Доказана нижняя оценка $L_{f_m}^+\ge m^{(C\log m)}$ ($C>0$). Библиогр. 7 назв.
Поступило: 10.01.1985
Образец цитирования:
А. А. Разборов, “Нижние оценки монотонной сложности логического перманента”, Матем. заметки, 37:6 (1985), 887–900; Math. Notes, 37:6 (1985), 485–493
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mzm5393 https://www.mathnet.ru/rus/mzm/v37/i6/p887
|
Статистика просмотров: |
Страница аннотации: | 1061 | PDF полного текста: | 304 | Первая страница: | 4 |
|