Sunday, August 15, 2010

P ≠ NP доказано?


http://www.vesti.ru/videos?vid=294623


...Проблема равенства классов сложности P и NP является одной из важнейших проблем теории алгоритмов...

...Предельно упрощённое описание классов P и NP выглядит так: P — это вычислительные задачи, которые легко решаются, а NP — те задачи, решение которых легко проверяется. Примером первого класса задач служит сортировка списка фамилий по алфавиту: очевидно, расположить в нужном порядке даже очень большое число элементов списка несложно...класс NP включает такие задачи, для которых легко проверить, является ли предлагаемое решение верным. Например, у вас есть код, вы не знаете алгоритма кодирования, но можете легко проверить... [является ли какая-либо определённая комбинация] правильным кодом...NP-задачи можно сравнить с пазлом, поскольку собрать его трудно, а проверка качества сборки занимает лишь пару секунд...

...Чтобы легче понять проблему, Математический институт Клэя приводит такой пример: вы должны разместить 400 студентов в 100 аудиториях. Декан снабдил вас списком, в котором перечислены пары студентов, не подходящих друг другу, и велел сделать так, чтобы ни в одной из аудиторий ни один студент не встретил ни одного другого студента, с которым находится в неприязненных отношениях.

Это и есть образец проблемы NP: легко проверить, будет ли составленная в результате разбивка на 100 аудиторий с именами студентов в них удовлетворять требованиям декана. Но задача по составлению такой разбивки, которая бы действительно устроила декана, практически нерешаема.

Общее количество операций, которые нужно произвести, чтобы оптимально заполнить 100 аудиторий студентами, превышает количество атомов в известной части Вселенной. Таким образом, невозможно построить такой суперкомпьютер, который сможет решить проблему "грубой силой" или простым перебором вариантов - всех комбинаций из 100 аудиторий со студентами.

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

...проблема P = NP состоит в следующем: если положительный ответ на какой-то вопрос можно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно быстро найти (за полиномиальное время и используя полиномиальную память)?.. то есть действительно ли задачу легче проверить, чем решить?..

...Учёный индийского происхождения Винай Деолаликар, работающий в Кремниевой долине, умудрился собрать доказательства для того, чтобы...решить ещё одну из семи задач тысячелетия...Его аргументация построена на задаче выполнимости булевых формул, которая заключается в следующем: можно ли назначить всем переменным, встречающимся в формуле, значения ложь и истина так, чтобы формула стала истинной. Эту задачу относят к разряду NP. Деолаликар утверждает, что нет такой программы, которая может с самого начала быстро выполнить такой подсчет, и поэтому этой проблеме нельзя придать статус P.

...Свои соображения Деолаликар представил на всеобщее обозрение в интернете...

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

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

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

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

http://cursorinfo.co.il/news/world/2010/08/11/matematic/
http://txt.newsru.com/arch/world/11aug2010/pversusnp.html
http://www.vesti.ru/doc.html?id=385309
http://www.gazeta.ru/news/science/2010/08/11/n_1532540.shtml
http://science.compulenta.ru/553934/
http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP
http://ru.wikipedia.org/wiki/Равенство классов P и NP
http://ru.wikipedia.org/wiki/Задачи тысячелетия

UPDATE 15-03-2012:

6 августа 2010 года сотрудник исследовательской лаборатории Hewlett-Packard в Пало-Альто Винэй Деолаликар разослал некоторым ученым на проверку своё доказательство неравенства P и NP. Стивен Кук назвал его препринт «относительно серьёзной попыткой решения проблемы P vs NP». Однако уже в том же месяце были найдены недостатки в доказательстве. Деолаликар заявил, что в следующей версии доказательства он постарается учесть все замечания.

На викистранице «Deolalikar P vs NP paper», связанной с проектом Polymath, приводится критический анализ, собраны предполагаемые ошибки и некоторые опечатки в работе Деолаликара. Там же можно проследить за онлайн-реакцией на предложенное доказательство.

http://ru.wikipedia.org/wiki/Равенство_классов_P_и_NP
END OF UPDATE

No comments:

Post a Comment