Решение «задачи тысячелетия» не верно?

Некоторые математики сомневаются в верности представленного Винэем Деолаликаром (Vinay Deolalikar) доказательства неравности классов задач P и NP, в виду возможных несоответствий.

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

Работа г-на Деолаликара на данный момент не направлена в научный журнал, а активно обсуждается в блогах профессиональных математиков Ричарда Липтона (Richard Lipton) из Технологического института Джорджии и Скотта Ааронсона (Scott Aaronson) из Массачусетского технологического института. В результате поиска ошибок и несоответствий в доказательстве Деолаликара коллеги Ричарда Липтона, Нил Иммерман (Neil Immerman) и Теренс Тао (Terence Tao),  первыми высказали свои замечания, обнаружив достаточно серьезные недочеты в обсуждаемой работе.

Так г-н Иммерман в своих замечаниях говорит о том, что господин Деолаликар нарушает правила «обращения»с набором FO(LFP), желая показать, что некоторые проблемы входят в класс NP, но в то же время не попадают в класс P. В свою очередь Теренс Тао обращает внимание на ошибки в доказательстве, связанные с задачей выполнимости булевых формул.

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

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

PostScriptum:
Хотите посмотреть захватывающий фильм про вампиров? Увлекательный фильм Блэйд смотреть онлайн бесплатно в любое удобное время можно на сайте www.vampiretv.ru.

Другие статьи:

Короткий URL: http://news4city.ru/?p=521

Написал в Фев 25 2010. Соответствие Разное. Вы можете перейти к обсуждениям записи RSS 2.0. Вы можете сделать trackback вашей записи

Ответить

Фотогалерея

Войти | Designed by Wordpress Themes