Новый Перельман
Aug. 11th, 2010 07:28 amУченый из США - математик Винай Деолаликар из лаборатории Hewlett-Packard в Пало-Альто, Калифорния - утверждает, что решил одну из математических "задач тысячелетия", доказав известное в информатике утверждение "Р не равно NP". Об этом сообщает The New Scientist (www.newscientist.com/article/dn19287-p--np-its-bad-news-for-the-power-of-computing.html). Это открытие позволит компьютерам решать многие задачи. Свои соображения Деолаликар представил на всеобщее обозрение в интернете (www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf). В случае подтверждения того, что Деолаликар решил задачу, он получит приз в 1 млн долларов от Математического института Клэя, поскольку данная задача - одна из семи проблем, за решение которых обещан такой приз.
Профессор Массачусетского института технологии Скотт Ааронсон настроен скептически: он взялся заплатить Деолаликару 200 000 долларов, если Институт Клэя утвердит его открытие. Профессор Ааронсон написал, что еле наскребет эту сумму, но пояснил: "Если проблема неравенства P и NP действительно решена, моя жизнь претерпит такой крутой поворот, что выплата двухсот тысяч долларов будет лишь самым незначительным событием в ней".
Чтобы легче понять проблему, Математический институт Клэя приводит такой пример: вы должны разместить 400 студентов в 100 аудиториях. Декан снабдил вас списком, в котором перечислены пары студентов, не подходящих друг другу, и велел сделать так, чтобы ни в одной из аудиторий ни один студент не встретил ни одного другого студента, с которым находится в неприязненных отношениях.
Это и есть образец проблемы NP: легко проверить, будет ли составленная в результате разбивка на 100 аудиторий с именами студентов в них удовлетворять требованиям декана. Но задача по составлению такой разбивки, которая бы действительно устроила декана, практически нерешаема.
Общее количество операций, которые нужно произвести, чтобы оптимально заполнить 100 аудиторий студентами, превышает количество атомов в известной части Вселенной. Таким образом, невозможно построить такой суперкомпьютер, который сможет решить проблему "грубой силой" или простым перебором вариантов - всех комбинаций из 100 аудиторий со студентами.
Профессор Массачусетского института технологии Скотт Ааронсон настроен скептически: он взялся заплатить Деолаликару 200 000 долларов, если Институт Клэя утвердит его открытие. Профессор Ааронсон написал, что еле наскребет эту сумму, но пояснил: "Если проблема неравенства P и NP действительно решена, моя жизнь претерпит такой крутой поворот, что выплата двухсот тысяч долларов будет лишь самым незначительным событием в ней".
Чтобы легче понять проблему, Математический институт Клэя приводит такой пример: вы должны разместить 400 студентов в 100 аудиториях. Декан снабдил вас списком, в котором перечислены пары студентов, не подходящих друг другу, и велел сделать так, чтобы ни в одной из аудиторий ни один студент не встретил ни одного другого студента, с которым находится в неприязненных отношениях.
Это и есть образец проблемы NP: легко проверить, будет ли составленная в результате разбивка на 100 аудиторий с именами студентов в них удовлетворять требованиям декана. Но задача по составлению такой разбивки, которая бы действительно устроила декана, практически нерешаема.
Общее количество операций, которые нужно произвести, чтобы оптимально заполнить 100 аудиторий студентами, превышает количество атомов в известной части Вселенной. Таким образом, невозможно построить такой суперкомпьютер, который сможет решить проблему "грубой силой" или простым перебором вариантов - всех комбинаций из 100 аудиторий со студентами.