Математик заявил о решении одной из задач тысячелетия

11-08-2010, 14:34 | Наука и техника / Новости науки и техники | разместил: VP | комментариев: (2) | просмотров: (4 007)

Винай Деолаликар. Фото с сайта hp.com

Индийский математик Винэй Деолаликар (Vinay Deolalikar) представил доказательства решения одной из так называемых задач тысячелетия, - ученый опубликовал 100-страничную статью, в которой сделан вывод, что классы сложности P и NP не равны. Препринт статьи в формате pdf можно скачать здесь, коротко о работе пишет New Scientist.

Вопрос о равенстве классов сложности P и NP можно сформулировать так: если положительный ответ на какой-то вопрос можно быстро проверить, то правда ли, что ответ на этот вопрос можно быстро найти? Эта задача чрезвычайно важна для компьютерных вычислений и прикладных наук, в частности для наук о шифровании данных. Например, если можно быстро проверить, является ли введенный шифр правильным, то можно ли достаточно быстро взломать этот шифр?

Доказательство, что классы сложности P и NP не равны, означает, что ответы на представленные выше два вопроса будут отрицательными. Иными словами, проверка шифра и его подбор являются задачами разного класса сложности.

В настоящее время экспертное сообщество не вынесло однозначного мнения по поводу статьи Деолаликара. Стоит ожидать, что оценки других математиков относительно строгости и правомерности доказательства начнут появляться после того, как будет опубликован окончательный вариант статьи. Планируется, что это произойдет в течение недели.

Задачи тысячелетия - это семь задач, за решение каждой из которых математический институт Клэя предлагает приз размером в один миллион долларов. Одной из таких задач было доказательство гипотезы Пуанкаре. Приз за решение этой задачи был присужден российскому математику Григорию Перельману, который, однако, отказался от денег, аргументировав это тем, что не согласен с решением института Клэя.

Источник: lenta.ru.

Рейтинг публикации:

Комментарии (2) | Распечатать

Добавить новость в:

Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь. Чтобы писать комментарии Вам необходимо зарегистрироваться либо войти на сайт под своим именем.

» #2 написал: VP (16 августа 2010 13:36)
Статус: |

Группа: Гости
публикаций 0
комментариев 0
Рейтинг поста:

Математики усомнились в решении задачи тысячелетия

     Математики из разных стран мира усомнились в правомерности доказательства одной из задач тысячелетия - вопросе о неравенстве классов сложности P и NP. Препринт статьи (pdf), в которой доказывалось, что они не равны, представил в начале августа индийский математик Винэй Деолаликар (Vinay Deolalikar). Официально статья пока не подана в реферируемый научный журнал.

      Деолаликар разослал препринт статьи нескольким ведущим математикам 6 августа 2010 года. Кроме того, по просьбе коллег ученый подготовил краткое описание своего доказательства и также выложил его в Сеть (pdf). Через несколько дней в блогах некоторых математиков появились записи, в которых они выражали сомнения в том, что Деолаликару действительно удалось строго доказать, что классы сложности P и NP не равны.

      Так, сотрудник Массачусетского технологического института (MIT) Скотт Ааронсон (Scott Aaronson) привел восемь причин, которые заставляют его думать, что Деолаликар не смог решить задачу тысячелетия. В частности, Ааронсон отмечает, что в своей статье Деолаликар не объясняет, почему его доказательство не работает для некоторых частных задач. Также ученый отмечает, что статья выдержана не в классическом стиле и в ней нет внятного краткого объяснения, почему новое доказательство смогло преодолеть барьеры, мешавшие математикам решить задачу тысячелетия раньше (такой обзор был дан в синопсисе, который Ааронсон, впрочем, считает малопонятным).

      Также не уверен в том, что работа Деолаликара окончательно доказывает, что классы сложности P и NP не равны, Ричард Липтон (Richard Lipton), который, как и Ааронсон, является одним из крупнейших специалистов в области, к которой относится задача тысячелетия. В своем блоге Липтон перечисляет несколько недочетов в доказательстве Деолаликара, которые, с высокой вероятностью, делают его неправомерным.

      Вопрос о равенстве или неравенстве классов сложности P и NP чрезвычайно важен для математики, а также для теории вычислений и наук о шифровании данных. Коротко эту проблему можно сформулировать так: если положительный ответ на какой-то вопрос можно быстро проверить, то правда ли, что ответ на этот вопрос можно быстро найти? Например, перед человеком стоит задача составить кратчайший маршрут путешествия между несколькими городами. После того как маршрут составлен, можно легко проверить, действительно ли он является самым коротким, однако решить эту задачу (она относится к классу сложности NP) за небольшое время невозможно.

      Если будет доказано, что классы сложности P и NP равны, то этот факт будет означать, что существует некий способ решить задачу о городах за разумное время (математики пользуются термином полиномиальное время). Подробнее прочесть о том, почему задача о равенстве классов сложности P и NP настолько важна (тот же Ааронсон обязался отдать Деолаликару 200 тысяч долларов, если его доказательство окажется верным), можно здесь. (Lenta.ru)

www-адрес статьи: http://www.inline.ru/gonews.asp?NewsID=205480

» #1 написал: VP (12 августа 2010 16:30)
Статус: |

Группа: Гости
публикаций 0
комментариев 0
Рейтинг поста:

Доказательство индийского математика ставит крест на быстрых вычислениях

11 августа, 20:30 | Алексей Тимошенко

Индийский математик Винэй Деолаликар, в настоящее время работающий в США, заявил о решении одной из сложнейших математических задач, входящих в список задач тысячелетия. Если он прав, то некоторые задачи математики никогда не смогут решать достаточно быстро.

Ученый, который сейчас работает в компании Hewlett-Packard, разослал своим коллегам письмо, к которому приложил 102-страничное доказательство того, что два класса математических задач— задачи классов NP и P не совпадают друг с другом. Если это утверждение верно, то последствия Долаликара не исчерпываются одним лишь миллионом долларов от Института Клэя, – из него также следует и то, что для решения некоторых задач никогда не удастся найти алгоритм, решающий их за мало-мальски приемлемое время.

Письмо Винэя Деолаликара

Желающие посмотреть на доказательство Деолаликара могут это сделать сами— pdf есть в открытом доступе.

P и NP на примере планирования отпуска и бухгалтерии

Что такое задача класса P? Это задача, которую можно решить сравнительно быстро, даже если модифицировать ее условия, добавив новые данные. Сложить вместе 10 или 11 чисел— невелика разница, поэтому подсчет суммы расходов или доходов за месяц относится к P-задачам.

асчет бухгалтерской отчетности (пример вымышленный) - пример P-задачи. Отметим, что P обозначает "полиномиальное время решения" - если в ведомости будет не 10, а 11 человек, то время расчета каких-либо показателей вырастет пропорционально числу сотрудников или, в худшем случае, пропорционально какой-нибудь степени этого числа.

А вот задача «найти кратчайший и самый дешевый способ объехать несколько городов»— пример задач другого класса, NP. Такие задачи могут быстро решаться при малом объеме входящих данных (когда надо найти самый недорогой путь от Москвы до Архангельска с заездом в Иваново), но их сложность растет с количеством входных данных не просто быстро, а очень быстро.

уточный комикс про задачу коммивояжера. При переборе "в лоб" сложность задачи растет как факториал (факториал 5 = 5*4*3*2*1, для остальных чисел по аналогии) числа городов, а использование динамических алгоритмов позволяет получить рост сложности задачи, пропорциональный произведению квадрата числа городов на двойку в степени этого числа. То есть для 10 городов будет (10*10)*(2-в 10-й степени) = 100*1024 = 102400 вариантов против 3628800 в случае перебора.

Источник: XKCD по-русски

В задаче о посещении нескольких городов, например, добавление к пяти пунктам шестого приводит к тому, что число возможных маршрутов умножается на шесть. Добавление к шести городам седьмого— на семь. Восьмого— на восемь, итого число вариантов получается таким:

Решение задачи методом перебора

Сколько городов надо объехать Число способов это сделать 2 2 (проехав туда и обратно) 3 2*3=6 4 6*4=24 5 24*5=120 6 120*6=720 7
n720*7=5040 8 5040*8=40320 ... ... 20 2432902010000000000
n

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

Пример упрощения

Как упростить задачу об объезде городов? Конкретный пример: надо посетить Ярославль, Кострому, Вологду, Сочи и Краснодар с минимальными затратами. Очевидно, что все варианты, где с юга страны на север надо перемещаться больше одного раза, здравомыслящие люди рассматривать не будут, поэтому число маршрутов резко сокращается. Также будут отброшены перелеты частным самолетом, а также поезда, в которых не окажется никаких мест кроме купе-люкс.

Но даже с такими упрощениями всем, кто планировал поездку по нескольким городам, известно что найти самый оптимальный вариант удается редко: так на бытовом уровне проявляет себя принадлежность «задачи коммивояжера» к NP-классу.

Возможно, в некоторых случаях просто нет подобающего алгоритма? Этот вопрос считается одним из фундаментальных вопросов современной математики и недаром отнесен к списку задач тысячелетия институтом Клэя. За решение этой проблемы, равно как за работу Григория Перельмана, готовы дать миллион долларов: достаточно скромная цена знания о том, можно ли хотя бы в принципе решить за приемлемое время некоторые задачи.

Они не равны? Ждем подтверждений.

Если Деолаликар прав, то некоторые задачи никогда не удастся решить за приемлемое время. Это значит, с одной стороны, что часть шифров по-прежнему будут надежно защищать информацию (их стойкость основана как раз на том, что взлом является NP-задачей), а с другой стороны некоторые проблемы так и останутся без решения. Навсегда, поскольку алгоритма, способного сравнительно быстро их решить, в принципе не появится.

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

Источник: Алексей Тимошенко, GZT.RU

Схожего мнения придерживались и придерживаются в настоящее время многие математики во всем мире, но одно дело догадка, а совсем другое— строгое доказательство. На анализ доказательства Деолаликара у специалистов уйдет некоторое время и впереди, безусловно, еще целый ряд комментариев со стороны других ученых. Знаменитое доказательство Перельмана, для сравнения, было представлено в 2003 году, а ряд работ, подтвердивших его корректность, вышли лишь в 2006-м. Вероятно, в случае с доказательством Деолаликара все может оказаться несколько быстрее, но вряд ли стостраничный труд по математике относится к числу текстов, предполагающих ускоренную экспертизу.

Квантовые компьютеры и шифры

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

NP-задачи квантовый компьютер сможет решать быстрее обычных машин.

Адрес статьи: http://www.gzt.ru/topnews/science/-dokazateljstvo-indiiskogo-matematika-stavit-k

rest-/319059.html

© 2001-2010 АНО Редакция ежедневной ГАЗЕТЫ

» Информация

Посетители, находящиеся в группе Гости, не могут оставлять комментарии к данной публикации. Зарегистрируйтесь на портале чтобы оставлять комментарии