О СЛОЖНОСТИ МУЛЬТИПЛЕКСОРНОЙ  ФУНКЦИИ В КЛАССЕ
π-СХЕМ
                             // Ученые записки КФУ. Физико-математические науки 2009 N2

Ложкин Сергей Андреевич; Власов Никита Вадимович

О СЛОЖНОСТИ МУЛЬТИПЛЕКСОРНОЙ ФУНКЦИИ В КЛАССЕ π-СХЕМ // Ученые записки КФУ. Физико-математические науки 2009 N2

Ложкин Сергей Андреевич, Власов Никита Вадимович

Дата публикации: 2009

Дата публикации в реестре: 2020-03-01T00:10:52Z

Аннотация:

Доказывается, что сложность реализации мультиплексорной функции порядка n в классе π-схем равна 2+ 2/n ± O(2/n log n), и, тем самым, для указанной сложности впервые устанавливаются так называемые асимптотические оценки высокой степени точности.

Тип: Article

Источник: ELIB18156088-2009-2-12