А. Е. Андреев, “Об одном методе получения более чем квадратичных эффективных нижних оценок сложности $\pi$-схем”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 1987, № 1, 70

Вестник Московского университета. Серия 1: Математика. Механика

RUS ENG

ЖУРНАЛЫ ПЕРСОНАЛИИ ОРГАНИЗАЦИИ КОНФЕРЕНЦИИ СЕМИНАРЫ ВИДЕОТЕКА ПАКЕТ AMSBIB

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

	Общая информация
	Последний выпуск
	Архив
	Импакт-фактор

	Поиск публикаций
	Поиск ссылок

	RSS
	Последний выпуск
	Текущие выпуски
	Архивные выпуски
	Что такое RSS

Вестн. Моск. ун-та. Сер. 1. Матем., мех.:
Год:
Том:
Выпуск:
Страница:
	Найти

Персональный вход:
Логин:
Пароль:
	Запомнить пароль
	Войти
	Забыли пароль?
	Регистрация

Вестник Московского университета. Серия 1: Математика. Механика, 1987, номер 1, страницы 70–73 (Mi vmumm3034)

Эта публикация цитируется в 4 научных статьях (всего в 5 статьях)

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

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

π

$\pi$ -схем

А. Е. Андреев

PDF полного текста (457 kB) Список цитирования (5)

Аннотация: В работе на основе обобщения метода Б. А. Субботовской (1961) и с использованием идеи универсальной функции Э. И. Нечипорука (1966) построен пример функции, имеющей в классе

π

$\pi$ -схем сложность реализации по порядку не менее чем

\frac{n^{5 / 2}}{(\log n)^{3 / 2} \log \log n},

$\frac{n^{5/2}}{(\log n)^{3/2}\log\log n},$
где

n

$n$ – число переменных. Самые высокие из известных ранее нижние оценки сложности реализации

π

$\pi$ -схемами индивидуальных функций имели рост

n^{2}

$n^2$ (В. М. Храпченко, 1971).
Библиогр. 5.

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

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

Тип публикации: Статья

УДК: 519.7

Образец цитирования: А. Е. Андреев, “Об одном методе получения более чем квадратичных эффективных нижних оценок сложности

π

$\pi$ -схем”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 1987, № 1, 70–73

Цитирование в формате AMSBIB

\RBibitem{And87}

\by А.~Е.~Андреев

\paper Об одном методе получения более чем квадратичных эффективных нижних оценок сложности $\pi$-схем

\jour Вестн. Моск. ун-та. Сер.~1. Матем., мех.

\yr 1987

\issue 1

\pages 70--73

\mathnet{http://mi.mathnet.ru/vmumm3034}

\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=0883632}

\zmath{https://zbmath.org/?q=an:0645.94022}

Образцы ссылок на эту страницу:

https://www.mathnet.ru/rus/vmumm3034

https://www.mathnet.ru/rus/vmumm/y1987/i1/p70

Эта публикация цитируется в следующих 5 статьяx:

С. Б. Гашков, И. С. Сергеев, “О значении работ В. М. Храпченко”, ПДМ, 2020, № 48, 109–124
А. Д. Коршунов, “Сложность вычислений булевых функций”, УМН, 67:1(403) (2012), 97–168 ; A. D. Korshunov, “Computational complexity of Boolean functions”, Russian Math. Surveys, 67:1 (2012), 93–165
А. Д. Коршунов, “Некоторые нерешенные задачи дискретной математики и математической кибернетики”, УМН, 64:5(389) (2009), 3–20 ; A. D. Korshunov, “Some unsolved problems in discrete mathematics and mathematical cybernetics”, Russian Math. Surveys, 64:5 (2009), 787–803
В. Б. Кудрявцев, А. Е. Андреев, “О сложности алгоритмов”, Фундамент. и прикл. матем., 15:3 (2009), 135–181 ; V. B. Kudryavtsev, A. E. Andreev, “On algorithm complexity”, J. Math. Sci., 168:1 (2010), 89–122
А. Д. Коршунов, “Монотонные булевы функции”, УМН, 58:5(353) (2003), 89–162 ; A. D. Korshunov, “Monotone Boolean functions”, Russian Math. Surveys, 58:5 (2003), 929–1001

Citing articles in Google Scholar: Russian citations, English citations
Related articles in Google Scholar: Russian articles, English articles

Статистика просмотров:
Страница аннотации:	166
PDF полного текста:	67

Что такое QR-код?

Обратная связь:

Пользовательское соглашение

Регистрация посетителей портала

Логотипы