УДК 519.7

О порядках роста функций Шеннона сложности схем над бесконечными базисами / О. М. Касим-Заде. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2013. № 3. С. 55-57.

Показано, что любая функция одного действительного переменного, выразимая в виде суперпозиции рациональных функций с действительными коэффициентами, логарифмов и экспонент и имеющая порядок роста не ниже n и не выше 2O(n1/2), является порядком роста функции Шеннона сложности схем над некоторым бесконечным базисом.

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

Библиогр. 13.

К оглавлению номера  Go!