Max Home IndustryВопрос о том, что P не равно NP (P≠NP), вероятно, самый важный в информатике, и за доказательство предлагается приз в 1 миллион долларов. Ожидание может закончиться, и одинокий исследователь из HP может получить доказательство на миллион долларов.
Проблема доказательства того, что P≠NP, вероятно, самая важная и хорошо известная проблема в информатике. (См. Статьи о том, что такое NP и P, в разделе «Дополнительная литература».)
Теперь Виней Деолаликар, известный исследователь в области теории сетей и сложности из HP Labs, выпустил статью, в которой утверждается, что P≠NP. По крайней мере, решение проблемы — это большая новость, потому что это одна из задач Премии тысячелетия и, следовательно, связана с призом в один миллион долларов для человека, который ее решит.
Деолаликер работал над проблемой в свободное время, и когда он, наконец, совершил «прорыв», он отправил статью по электронной почте ряду различных «ведущих исследователей» в различных областях. Новость была опубликована в неофициальном блоге, а статья была опубликована в сети, очевидно, без ведома Деолаликара. Вы можете прочитать статью по ссылке ниже.
Конечно, большинство компьютерных ученых давно считали, что NP отличается от P — это кажется разумным, что так и должно быть. Однако в прошлом давно устоявшиеся «верования» были опровергнуты, когда было обнаружено настоящее доказательство, и поэтому было и, возможно, все еще есть мучительные сомнения в том, что NP и P могут быть одним и тем же. Если бы это было так, то последствия могли бы быть серьезными, поскольку большинство кодексов основано на различии.
В настоящее время статус статьи не определен — доказательство или недоработка. Обычно вопросы такого рода решаются коллегами, и это может занять время. Интернет ускорил процесс, но он также усложнил задачу узнать, когда ошибочное или даже ненормальное доказательство приветствуется как решение некоторых престижных проблем.
В этом случае у автора есть подходящий послужной список. Вместе с другими исследователями он доказал, что P меньше NP для машин Тьюринга с бесконечным временем. Это снижает вероятность того, что статья является подделкой, но до вынесения окончательного вердикта пройдет еще некоторое время.
Наиболее достоверное с академической точки зрения обсуждение статьи можно найти в блоге профессора Ричарда Липтона. Доказательство того, что P≠NP?
Деолаликер заявляет, что окончательная версия статьи будет доступна на его веб-странице примерно через неделю.
На данный момент ранний черновик можно прочитать на pnp12pt.pdf.