УДК 519.7
О порядках роста функций Шеннона сложности схем над бесконечными базисами / О. М. Касим-Заде. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2013. № 3. С. 55-57.
Показано, что любая функция одного действительного переменного, выразимая в виде суперпозиции рациональных функций с действительными коэффициентами, логарифмов и экспонент и имеющая порядок роста не ниже n и не выше 2O(n1/2), является порядком роста функции Шеннона сложности схем над некоторым бесконечным базисом.
Ключевые слова: булева функция, схема из функциональных элементов, сложность, функция Шеннона.
Библиогр. 13.
