|
Вестник Московского университета. Серия 1: Математика. Механика, 2020, номер 3, страницы 42–46
(Mi vmumm4327)
|
|
|
|
Краткие сообщения
Многоярусное представление и сложность схем из многовходовых элементов
И. С. Сергеев ФГУП НИИ "Квант", г. Москва
Аннотация:
Получено новое более простое доказательство асимптотики $C(n)\sim\sqrt2\cdot 2^{n/2}$ функции Шеннона сложности схем в базисе из многовходовых элементов обобщенных конъюнкций.
Ключевые слова:
булевы функции, схемы из функциональных элементов, сложность, многоярусное представление.
Поступила в редакцию: 28.02.2018
Образец цитирования:
И. С. Сергеев, “Многоярусное представление и сложность схем из многовходовых элементов”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2020, № 3, 42–46; Moscow University Mathematics Bulletin, 75:3 (2020), 121–125
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vmumm4327 https://www.mathnet.ru/rus/vmumm/y2020/i3/p42
|
Статистика просмотров: |
Страница аннотации: | 123 | PDF полного текста: | 29 | Список литературы: | 26 | Первая страница: | 1 |
|