И. С. Сергеев, “Многоярусное представление и сложность схем из многовходовых элементов”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2020, номер 3,страницы 42

Краткие сообщения

Многоярусное представление и сложность схем из многовходовых элементов

И. С. Сергеев

ФГУП НИИ "Квант", г. Москва

Аннотация: Получено новое более простое доказательство асимптотики $C(n)\sim\sqrt2\cdot 2^{n/2}$ функции Шеннона сложности схем в базисе из многовходовых элементов обобщенных конъюнкций.

Ключевые слова: булевы функции, схемы из функциональных элементов, сложность, многоярусное представление.

УДК: 519.714

Поступила в редакцию: 28.02.2018