|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
О сложности схем и формул ограниченной глубины над базисом из многовходовых элементовстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАКДата последнего поиска статьи во внешних источниках: 16 января 2019 г.
- Автор: Сергеев И.С.
- Журнал: Дискретная математика
- Том: 30
- Номер: 2
- Год издания: 2018
- Издательство: ФГБУ "Издательство "Наука"
- Местоположение издательства: Москва
- Первая страница: 120
- Последняя страница: 137
- DOI: 10.4213/dm1449
- Аннотация: Получены оценки сложности реализации булевых функций n переменных схемами и формулами, использующими многовходовые функциональные элементы конъюнкции и дизъюнкции и либо элементы отрицания, либо отрицания переменных в качестве входов. Дополнительно накладываются ограничения на глубину схем или формул. В ряде случаев полученные оценки оказываются асимптотически точными. В частности, для сложности схем с переменными и их отрицаниями на входах получена асимптотика функции Шеннона 2⋅2^(n/2), которая достигается на схемах глубины 3.
- Добавил в систему: Сергеев Игорь Сергеевич
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | Полный текст | DM_2018.pdf | 654,1 КБ | 1 июля 2021 [isserg] |