Воскресенье, 18 августа, 23:04
Публикации / Аудитория №1
Вопрос на миллион... долларов
27.09.12 07:16 / Аудитория №1   Просмотров: 8606   Автор: Олег Владимиров
рейтинг: 3.09   версия для печати послать другу

Задачу тысячелетия, более известную как задача коммивояжёра, решил Анатолий Плотников, математик из Луганска. За решение обещана премия в миллион долларов. Хотя ошибки в решении пока не нашли, премии тоже не дали. А она бы математику точно не помешала. Анатолий Плотников, профессор Восточноукраинского национального университета, живет в общежитии, его зарплаты на решение жилищных проблем не хватает.

Математик-1 Задача коммивояжера - одна из самых известных комбинаторных задач, заключающаяся  в отыскании самого оптимального маршрута. Условий, которые учитываются в задаче, как и в реальной жизни коммивояжера, много: начиная от выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и заканчивая тем, что он должен проходить через указанные города хотя бы по одному разу с последующим возвратом в исходный город. Даже при небольшом количестве городов (несколько десятков), чтобы решить задачу методом подбора вариантов, компьютеру понадобится несколько миллионов (!) лет. Учитывая, что данный конкретный коммивояжер столько ждать не может, а у другого (через миллионы лет) будут другие города и маршруты, встает вопрос, а способен ли справиться электронный мозг с подобными задачками. Проблему можно обозначить и по-другому: все ли задачи имеют решение.

Справедливости ради надо отметить, что задача коммивояжера встала перед человечеством раньше, чем появились компьютеры - первые попытки её решить предпринимались еще в 19 веке. Однако с появлением электронно-вычислительных машин она приобрела новое звучание.   

«P против nP» - так условно называют проблему сегодня. Она вошла в число семи «задач тысячелетия», математических проблем, на которые найти ответы до сих пор не удавалось.

Проблема «P vs nP» в том, может ли существовать эффективный алгоритм для решения  каждой из всего множества компьютерных задач. Эти задачи назвали классом nP. Часть этого множества - класс P - задачи, для которых эффективный алгоритм определенно существует. Но равно ли множество P множеству nP, или же они не совпадают - в этом заключается суть проблемы, которую удалось разрешить луганскому математику.

Математик-2 Анатолий Плотников, используя теорию множеств, доказал, что класс Р не равен nP, а значит, алгоритм можно найти не к каждой из компьютерных задач. В процессе решения некоторых задач nP в течение небольшого отрезка времени могут появляться промежуточные результаты, подобные задачи можно включить в подкласс UF. В то же время все остальные задачи nP могут требовать значительно большего времени для получения промежуточного результата. При этом класс P является подмножеством UF, но UF не равен nP. ?з этого следует, что классы P и nP не равны.

Решение «задачи тысячелетия» Анатолий Плотников опубликовал в американском «Журнале компьютерных наук» в мае нынешнего года. Однако в Украине публикацией заинтересовались только сейчас, когда стало известно, что американский математический институт Клэя назначил за решение премию в один миллион долларов.

Анатолий Плотников - профессор Восточноукраинского национального университета. В Луганск несколько лет назад приехал преподавать из Харькова. Квартиру профессору университет пока не выделил, он до сих пор живет в одной из комнат студенческого общежития. Быт совершенно спартанский: койка с пружинным матрасом, шкаф для одежды, кухонный стол и стол рабочий. Кухня и умывальник - в конце длинного общежитского коридора.

- После публикации прошло пять месяцев, ошибок в доказательстве не нашли, - говорит Анатолий Плотников. - Миллион пока никто не предлагал. Я бы от него не отказался, от квартиры точно не откажусь. А основную часть отдал бы детям, чтобы они могли совершенствоваться, жить нормально. А если денег не будет, переживать не стану. Главное - удалось решить задачу.

Решение задачи коммивояжера имеет огромное прикладное значение: от разработки оптимального маршрута для коммивояжера (и вообще оптимальной логистики где бы то ни было) до расшифровки криптографических задач, моделирования физических и химических процессов, ответов на многие вопросы генетики.

Впрочем, учитывая, что ответ луганского ученого на задачу тысячелетия отрицательный - P не равно nP, значит, сняв один вопрос с «повестки тысячелетия», человечеству придется искать новые пути решения тысяч других вопросов. 

Олег Владимиров

 

 

Читайте также:



Комментарии:
Уважаемые посетители сайта! На протяжении длительного времени форум «Недели» был самой демократичной и открытой для дискуссий площадкой в нашем регионе. Но сегодня, когда социальное и политическое напряжение в обществе растет, а слово перестало быть просто словом, и становится пусковым механизмом для эскалации напряженности, мы вынуждены временно закрыть возможность комментирования.

Редакция «Недели» несет ответственность за весь контент сайта, и мы не хотим, чтобы неосторожные слова, сказанные на нём, стали причиной реальных конфликтов.

При этом сегодня нам как никогда важно ваше мнение обо всем происходящем. Мы предлагаем перенести споры, дискуссии, мнения в социальные сети - в наши группы ВКонтакте, Фейсбук, Одноклассники, Твиттер, где также доступны все наши новости.

Верим в скорое разрешение конфликта и желаем вам мира.



Видео
Украинский Щедрик идет по миру
     Новости









     Блоги
25 сентября 2014 года алчевский троллейбус встретил своё 60-летие. Официальных торжеств по этому по...
Патриотическое искуcство требует внимания. ...
Бойцы с полосатыми ленточками сделали то, что никогда бы не смогли даже самые лютые бандеровцы – фак...
О том , откуда берутся коллективных мифы и как работает считаное сознание ...
Немного пятничных котиков...
Удержаться не могу. Просто достали. Я ни на что не претендую. Выводы думаю, каждый сделает сам. ...
     Последние объявления
Новости от KINOafisha.ua
Загрузка...
Загрузка...
Курсы валют
Loading...