RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Московского университета. Серия 1: Математика. Механика // Архив

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2013, номер 3, страницы 55–57 (Mi vmumm409)

Эта публикация цитируется в 1 статье

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

О порядках роста функций Шеннона сложности схем над бесконечными базисами

О. М. Касим-Заде

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

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

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

УДК: 519.7

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


 Англоязычная версия: Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2013, 68:3, 170–172

Реферативные базы данных:


© МИАН, 2024