Нижняя оценка немонотонной сложности функций многозначной логики

АБВ
АБВ
АБВ

Обычная версия сайта

Приоритетные направления

по году

Тематика

31 июля 2026 г.

«Я всегда занимаюсь исследованиями на темы, которые меня по-настоящему волнуют»

Анастасия Деева изучает социально-экономические последствия избыточного веса в России. В интервью проекту «Молодые ученые Вышки» она рассказала о том, что красоту невозможно измерить, о желании написать роман, «достоевском» выгорании и работе в отеле, где снималось «Сияние».

30 июля 2026 г.

Два года роста или падения: как выбрать инвестиционную стратегию

Экономисты из НИУ ВШЭ совместно с коллегами из зарубежных университетов изучили движение биржевых цен за почти 100 лет и предложили инвестиционную стратегию, доходность которой почти вдвое могла бы превысить рыночную. Ученые предлагают придерживаться стратегии моментум, когда рынок растет в течение двух лет, и переключаться на стоимостный подход, когда рынок падает. Статья опубликована в ведущем международном журнале Journal of Banking and Finance.

28 июля 2026 г.

Исследователи ВШЭ показали связь между вниманием и трудностями общения при аутизме

Исследователи НИУ ВШЭ изучили, как трудности в общении детей с аутизмом связаны с работой мозга. Данные показали, что важную роль играют не только языковые сети, но и сети внимания. Чем хуже работали связи, поддерживающие фокус и переключение внимания, тем более выраженными были нарушения в коммуникации. Исследование опубликовано в журнале European Child & Adolescent Psychiatry.

Нашли опечатку?
Выделите её, нажмите Ctrl+Enter и отправьте нам уведомление. Спасибо за участие!

Публикации

?

Нижняя оценка немонотонной сложности функций многозначной логики

С. 76–79.

Кочергин В. В., Михайлович А. В.

Установлена нижняя оценка немонотонной сложности функций многозначной логики, отличающающаяся от известной верхней оценки не более чем на абсолютную константу

Язык: русский

В книге

Материалы XIV Международного семинара "Дискретная математика и ее приложения" имени академика О.Б.Лупанова (Москва, МГУ, 20-25 июня 2022 г.)

М.: Институт прикладной математики им. М.В. Келдыша РАН, 2022.

The Exact Circuit Complexity of Boolean Functions in an Infinite Basis

V. V. Kochergin, A. V. Mikhailovich, Mathematical notes 2025 Vol. 117 No. 4 P. 579–594

Добавлено: 28 февраля 2026 г.

Точное значение схемной сложности булевых функций в одном бесконечном базисе

Кочергин В. В., Михайлович А. В., Математические заметки 2025 Т. 117 № 4 С. 523–542

Для каждой булевой функции установлено точное значение сложности реализации логическими схемами в бесконечном базисе, состоящем из отрицания и всех монотонных булевых функций. Под сложностью функции понимается минимально возможное число элементов базиса, достаточное для построения схемы для данной функции. ...

Добавлено: 8 апреля 2025 г.

Математические вопросы кибернетики. Вып. 22

Михайлович А. В., Кочергин В. В., М.: Физматлит, 2024.

Добавлено: 10 марта 2025 г.

Improvement of Nonmonotone Complexity Estimates of k-Valued Logic Functions

Кочергин В. В., Михайлович А. В., Mathematical notes 2023 Vol. 113 No. 5 P. 794–803

Добавлено: 19 ноября 2023 г.

Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games

Игнатьев А. А., Mihajlin I., Smal A., , in: 33rd International Symposium on Algorithms and Computation (ISAAC 2022). LIPIcs, Volume 248.: Saarbrücken, Вадерн: Schloss-Dagstuhl - Leibniz Zentrum für Informatik, 2022. Ch. 66.

Добавлено: 9 ноября 2023 г.

Сравнение оценок сложности для задач Р. Беллмана и О. Б. Лупанова

Кочергин В. В., В кн.: Материалы XIV Международного семинара "Дискретная математика и ее приложения" имени академика О.Б.Лупанова (Москва, МГУ, 20-25 июня 2022 г.).: М.: Институт прикладной математики им. М.В. Келдыша РАН, 2022. С. 4–16.

Задача Беллмана является обобщением классической задачи об эффективном возведении в степень, т.\,е. задачи о нахождении величины $l(x^n)$ --- минимального числа операций умножения, достаточного для вычисления по переменной $x$ величины $x^n$, при этом вычислительная модель допускает возможность многократного использования результатов промежуточных вычислений. Задача Лупанова заключается в нахождении сложности вычисления элемента конечной абелевой группы по ее образующим. Значение ...

Добавлено: 29 октября 2022 г.