|
О сложности и глубине схем, реализующих частичные булевы функции
А. В. Чашкин
Аннотация:
Изучается сложность и глубина схем, реализующих частичные булевы функции в предположении $FP\neq NC$. При этом предположении устанавливается существование частичных булевых функций, для которых не существует схем, сложность и глубина которых одновременно близки к минимально возможным, т.е. у любой схемы, реализующей одну из таких функций, либо глубина, либо сложность значительно превосходит соответственно либо глубину, либо сложность реализуемой функции.
Статья поступила: 30.09.1994
Образец цитирования:
А. В. Чашкин, “О сложности и глубине схем, реализующих частичные булевы функции”, Дискрет. матем., 9:2 (1997), 53–58; Discrete Math. Appl., 7:2 (1997), 113–118
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm463https://doi.org/10.4213/dm463 https://www.mathnet.ru/rus/dm/v9/i2/p53
|
Статистика просмотров: |
Страница аннотации: | 572 | PDF полного текста: | 416 | Первая страница: | 1 |
|