Размер:
A A A
Цвет: C C C
Изображения Вкл.Выкл.
Обычная версия сайта
Demidov Yaroslavl State University
11/01/2018

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

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

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

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

Источник: Мангазея

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