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