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

Андрей Николаев: «Если кто-то решит задачу, которая появилась в 1832 году, математики в современном понимании больше не будет»

13/09/2017
Андрей Николаев: «Если кто-то решит задачу, которая появилась в 1832 году, математики в современном понимании больше не будет»


- NP-трудные задачи – известная вещь. В 2000 году эксперты Математического института Клея сформулировали семь математических проблем, за решение каждой из которых полагается премия – миллион долларов, - рассказывает Андрей Николаев, доцент кафедры дискретного анализа факультета ИВТ ЯрГУ, который только что возвратился с европейской конференции по комбинаторике, теории графов и приложениям «Eurocomb - 2017»*. – На сегодняшний день из семи задач решена только одна – гипотеза Пуанкаре, и решил ее Григорий Перельман.


- Какую из 7 задач решаете вы?

- Мы занимаемся задачей коммивояжера; существует ли для ее решения хороший алгоритм или нет, пока никто не знает.

- В чем суть этой задачи?

- Это одна из самых известных задач. Есть некий набор городов и расстояний между парами городов; коммивояжер должен объехать эти города, посещая каждый ровно один раз. Задача – построить ему маршрут минимальной длины.

- Условия задачи взяты из повседневной жизни!

- Да, например, служба доставки должна развезти груз. Есть 20 пунктов доставки в виде точек на карте Ярославля. Необходимо установить, в каком порядке следует объезжать эти пункты, чтобы минимизировать время доставки.

- Неужели это так сложно?

- Очень. Для 20-30 точек маршрут легко проложит даже навигатор в телефоне, а, к примеру, для маршрута из 1000 точек это сделать очень сложно.

- Что же удалось сделать вам?

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

- То есть вы идете от исключения?

- Да, мы исключаем классы алгоритмов, которые не работают на решение этой задачи. Конечно, было бы здорово построить алгоритм, который работает, но их почти наверняка не существует. Хотя есть люди, которые пытаются доказать, что они существуют.

- Почему вы уверены, что таких алгоритмов нет?

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

- ???

- Именно так. Любую теорему можно будет доказать на компьютере: ввести набор аксиом, правила вывода и некое утверждение. Если утверждение следует из аксиом, то компьютер автоматически построит цепочку логических переходов, ведущих к утверждению и докажет, что оно истинно. Ведь в случае равенства классов P и NP между проверкой готового доказательства и построением доказательства «с нуля» не будет принципиальной разницы.

- Мне кажется, математики сами роют себе яму. Что заставляет их придумывать такие задачи?

- Они их не придумывают, их ставит перед ними сама жизнь. За последние 40 лет подобных задач описаны тысячи. С ними даже студенты сталкиваются на занятиях: например, нужно составить расписание занятий. По сложности эта задача не уступает задаче коммивояжера. Нужно распределить занятия так, чтобы в каждой аудитории был один поток, а не пять, чтобы ни у преподавателя, ни у студентов не было пяти пар в одно и то же время, чтобы потоковые лекции не оказались в аудитории на 20 человек, чтобы занятия по программированию проводились в компьютерных аудиториях и т.д.

- И как, справились студенты с этой задачей?

- Есть хорошая новость и плохая. Подавляющее большинство математиков и специалистов по компьютерным наукам убеждены в том, что классы P и NP не равны, а, следовательно, труднорешаемые задачи существуют. С одной стороны, это изрядно усложняет жизнь, как с тем же составлением расписания занятий. Так как подобные задачи решать всё равно приходится, то применяются различные эвристические и приближённые алгоритмы. Мы уже не ищем оптимального решения, которое очень сложно построить, а пытаемся найти некоторое «достаточно хорошее» решение, которое нас устроит. С другой стороны, хорошая новость заключается в том, что односторонние функции вероятно существуют, а значит криптография работает и жизнь продолжается, как и прежде.

Беседовала Юлия Цофина.

 * Eurocomb – это одна из самых престижных конференций в Европе по комбинаторике и дискретной математике. В этом году конференция проходила в Венском техническом университете. Тематика докладов на Eurocomb лежит на стыке чистой математики и компьютерных наук. С одной стороны, теоретические результаты используются для разработки точных и приближенных алгоритмов для маршрутизации транспорта, составления расписаний, проектирования микрочипов и т.д. С другой стороны, практические приложения часто порождают интересные теоретические задачи. В последнее время популярной областью в теории графов стало исследование графов, которые моделируют структуру Интернета или социальных сетей. Здесь задачи варьируются от изучения предпочтений пользователей до анализа распространения интернет-мемов. Этой областью занимаются исследовательские отделы Яндекс и Google. 

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

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


Август 2017
Пн Вт Ср Чт Пт Сб Вс
31 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 1 2 3
Управление научных исследований и инноваций (УНИ) ЯрГУ

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

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

Время работы

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