Доказательство P≠NP

Вопрос о том, что P не равно NP (P≠NP), вероятно, самый важный в информатике, и за доказательство предлагается приз в 1 миллион долларов. Ожидание может закончиться, и одинокий исследователь из HP может получить доказательство на миллион долларов.

Доказательство P≠NP

Проблема доказательства того, что P не равно NP, вероятно, самая важная и хорошо известная проблема в информатике. (См. Статьи о том, что такое NP и P, в разделе «Дополнительная литература».)

Теперь Виней Деолаликар, известный исследователь в области теории сетей и сложности из HP Labs, выпустил статью, в которой утверждается, что P не равно NP. По крайней мере, решение проблемы – это большая новость, потому что это одна из задач Премии тысячелетия и, следовательно, связана с призом в один миллион долларов для человека, который ее решит.

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

Конечно, большинство компьютерных ученых давно считали, что NP отличается от P – это кажется разумным, что так и должно быть. Однако в прошлом давно устоявшиеся «верования» были опровергнуты, когда было обнаружено настоящее доказательство, и поэтому было и, возможно, все еще есть мучительные сомнения в том, что NP и P могут быть одним и тем же. Если бы это было так, то последствия могли бы быть серьезными, поскольку большинство кодексов основано на различии.

В настоящее время статус статьи не определен – доказательство или недоработка. Обычно вопросы такого рода решаются коллегами, и это может занять время. Интернет ускорил процесс, но он также усложнил задачу узнать, когда ошибочное или даже ненормальное доказательство приветствуется как решение некоторых престижных проблем.

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

Наиболее достоверное с академической точки зрения обсуждение статьи можно найти в блоге профессора Ричарда Липтона. Доказательство того, что P не равно NP?

Деолаликер заявляет, что окончательная версия статьи будет доступна на его веб-странице примерно через неделю.

На данный момент ранний черновик можно прочитать на pnp12pt.pdf.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *