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

Дискрет. матем., 1997, том 9, выпуск 2, страницы 53–58 (Mi dm463)

О сложности и глубине схем, реализующих частичные булевы функции

А. В. Чашкин


Аннотация: Изучается сложность и глубина схем, реализующих частичные булевы функции в предположении $FP\neq NC$. При этом предположении устанавливается существование частичных булевых функций, для которых не существует схем, сложность и глубина которых одновременно близки к минимально возможным, т.е. у любой схемы, реализующей одну из таких функций, либо глубина, либо сложность значительно превосходит соответственно либо глубину, либо сложность реализуемой функции.

УДК: 519.7

Статья поступила: 30.09.1994

DOI: 10.4213/dm463


 Англоязычная версия: Discrete Mathematics and Applications, 1997, 7:2, 113–118

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


© МИАН, 2024