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

Дискрет. матем., 2013, том 25, выпуск 2, страницы 82–84 (Mi dm1236)

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

Упрощенное доказательство одной нижней оценки сложности

В. М. Храпченко


Аннотация: Значительно упрощено доказательство одного известного неравенства, позволяющего получать квадратичные нижние оценки сложности $\Pi$-схем (или, что то же самое, формул над базисом $\{\&,\vee,\bar{}\ \}$) для многих булевых функций.
Работа выполнена при финансовой поддержке Программы фундаментальных исследований ОМН РАН “Алгебраические и комбинаторные методы математической кибернетики”, проект “Синтез и сложность управляющих систем”.

УДК: 519.95

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

DOI: 10.4213/dm1236


 Англоязычная версия: Discrete Mathematics and Applications, 2013, 23:2, 171–174

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


© МИАН, 2024