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

АБВ
АБВ
АБВ

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

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

по году

Тематика

6 октября 2026 г.

Пользователи теряют выгоду от ограничения сбора и обработки персональных данных

Экономист НИУ ВШЭ c помощью микроэкономической модели показала, что чрезмерно строгие ограничения на сбор и обработку персональных данных приносят пользователям больше вреда, чем пользы. Статья опубликована в журнале «Вопросы экономики».

5 октября 2026 г.

«Среди детей с задержкой развития устной речи 40% сталкиваются с трудностями при чтении и письме»

5 октября — День осведомленности о дислексии. С этим нарушением чтения, по разным оценкам, сталкиваются от 5 до 20% людей. В Центре языка и мозга НИУ ВШЭ не только изучают дислексию, но и создают цифровые инструменты для логопедов и нейропсихологов — «ЛексиМетр», «ЗАРЯ», «КОРАБЛИК» и другие, а родителям объясняют, как вовремя заметить трудности. Старший научный сотрудник центра Светлана Дорофеева рассказала, как отличить дислексию от лени и что на самом деле помогает.

2 октября 2026 г.

В НИУ ВШЭ обсудили этические границы взаимодействия человека и антропоморфного робота

В Высшей школе экономики состоялся экспертный семинар Центра этики и онтологии роботов Института робототехнических систем (ИРС), посвященный разработке практических требований к проектированию и безопасному внедрению антропоморфных роботов. Участники обсудили, как перевести этические принципы в технические параметры, протоколы проверки и требования к эксплуатации робототехнических систем.

Нашли опечатку?
Выделите её, нажмите 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 г.