?

Log in

No account? Create an account

КНiЖНЫЙ ШКАПъ

History

11th August 2010

5:39pm: В США появился собственный Перельман: математик решил еще одну "задачу тысячелетия"
Но "наш Перельман" отказался от денег...
------
Новость:
"Ученый из США утверждает, что решил одну из математических "задач тысячелетия". Математик Винай Деолаликар из лаборатории Hewlett-Packard в Пало-Альто, Калифорния, уверен, что доказал известное в информатике утверждение "Р не равно NP", сообщает The New Scientist. ..

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

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

Общее количество операций, которые нужно произвести, чтобы оптимально заполнить 100 аудиторий студентами, превышает количество атомов в известной части Вселенной. Таким образом, невозможно построить такой суперкомпьютер, который сможет решить проблему "грубой силой" или простым перебором вариантов - всех комбинаций из 100 аудиторий со студентами.
Но на самом деле одна из выдающихся проблем информатики в том, чтобы определить, есть ли такие вопросы, ответы на которые можно быстро проверить, но которые требуют невозможно долгого времени на решение каким-либо непосредственным способом. .."
http://www.newsru.com/world/11aug2010/pversusnp.html
----

Чего только не придумают, чтобы заставить "нашего Перельмана" взять 1 млн $, а то "мировая общественность" успокоиться не может :) - Тесно им жить на планете рядом с ИЗВЕСТНЫМ бессребренником! На неизвестных они плюют, а вот известных, да еще и умных, им допустить никак нельзя, так как их собственная неправедность очень в глаза лезет и ... спать мешает!
Powered by LiveJournal.com