Ярославский государственный университет им. П.Г.Демидова
тел./ факс: +7(4852) 79-77-51
Научная деятельность Документы Подразделения научного управления Молодежная наука

Ученый ЯрГУ получил грант Президента РФ

11/01/2018
Ученый ЯрГУ получил грант Президента РФ

Совет по грантам Президента РФ определил победителей конкурса 2018 года по государственной поддержке молодых российских ученых-кандидатов наук. В числе победителей – Андрей Николаев, кандидат физико-математических наук, доцент кафедры дискретного анализа факультета ИВТ ЯрГУ им. П.Г. Демидова.

Молодой ученый получил грант на выполнение проекта «Комбинаторно-геометрический анализ труднорешаемых задач». Речь идет о задаче соотношения классов сложности P и NP, одной из фундаментальных нерешённых задач в прикладной математике и фундаментальной информатике. Математический институт Клэя включил её в список семи математических задач тысячелетия. Комбинаторно-геометрический анализ предлагает перспективный подход к анализу сложности задач и построению нижних оценок для конкретных моделей вычислений и классов алгоритмов, а также к разработке новых точных и аппроксимационных алгоритмов. В своем исследовании Андрей Николаев планирует изучить новые подходы к анализу комбинаторных задач, описать новые полиномиально разрешимые подклассы труднорешаемых задач и разработать принципиально новые алгоритмы комбинаторной оптимизации.

Андрей Николаев: «В двух словах задачу соотношения классов сложности P и NP можно сформулировать так: существует ли принципиальная разница в сложности между решением задачи и проверкой решения? На первый взгляд ответ интуитивно очевиден. Однако в действительности его никто не знает. Более того, из теории NP-трудных задач следует, что если существует эффективный алгоритм для хотя бы одной задачи, например, для задачи коммивояжера, то эффективные алгоритмы существуют для любой задачи, решение которой можно быстро проверить. Последствия такого результата были бы очень занимательны. Во-первых, было бы доказано, что не существует односторонних функций. Односторонняя функция – это функция, которая в одну сторону считается легко, в другую – сложно. Односторонние функции являются фундаментальными инструментами криптографии: зашифровать что-то легко, а расшифровать, если не знать ключ, сложно. Решение любой из NP-трудных задач будет означать, что односторонних функций просто не существует: всё, что можно зашифровать, так же легко можно и расшифровать. И здесь речь идёт не только о тайне переписки. Подобный результат сразу «убьет» интернет, банковскую систему и т.п. Мы не сможем расплатиться картой: транзакцию можно будет перехватить на любом узле, и деньги уйдут куда угодно. Кроме того, математики в современном понимании тоже не будет.»

Полный текст интервью с Андреем Николаевым здесь. 

ВКонтакт Facebook Google Plus Одноклассники Twitter Яндекс Livejournal Liveinternet Mail.Ru

Возврат к списку


Январь 2018
Пн Вт Ср Чт Пт Сб Вс
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 1 2 3 4
Управление научных исследований и инноваций (УНИ) ЯрГУ

+7(4852) 79-77-51
nis@uniyar.ac.ru

Ярославль,
ул. Советская, 14, к. 305
посмотреть на карте

Время работы

с 8:30 до 17:30,
обед с 12:30 до 13:30