Главная страница » Новости науки » В США появился собственный Перельман

В США появился собственный Перельман

11.08.2010
В США появился собственный Перельман

Ученый из США утверждает, что решил одну из математических "задач тысячелетия". Математик Винай Деолаликар из лабораторий Hewlett-Packard в Пало-Альто, Калифорния уверен, что доказал известное в информатике утверждение "Р не равно NP", сообщает The New Scientist.
Это открытие позволит компьютерам решать многие задачи. В случае его подтверждения Деолаликар получит приз в 1 млн долларов от Математического института Клэя, поскольку данная задача - одна из семи проблем, за решение которых обещан такой приз.
Последним, кто решил одну из "задач тысячелетия", оказался российский математик Григорий Перельман. Ученый-эксцентрик из Санкт-Петербурга живет затворником и практически не общается с коллегами. Свое доказательство гипотезы Пуанкаре, над которой около ста лет ломали голову лучшие умы мировой математики, он опубликовал в интернете. Когда же Перельману предложили получить премию в миллион долларов, он отказался и даже не приехал на церемонию награждения за символическим призом.
Вопрос "P и NP" относится к скорости, с которой компьютер решает такую задачу, как, например, разложение числа на множители. Некоторые задачи могут решаться за достаточно короткий период времени, поскольку продолжительность их решения пропорциональна объему введенной информации. Эти задачи включены в класс P.
Если ответ можно проверить быстро, тогда эта задача находится в классе NP. Так что если P=NP, то каждая задача, решение которой можно проверить быстро, соответственно, может быть и решена с высокой скоростью. Этот вывод может иметь весьма серьезные последствия для обеспечения безопасности в интернете, где трудности при разложении на множители очень больших чисел являются основным барьером, который выставляют на пути хакеров.
Но Деолаликар не согласен с этим. Его аргументация построена на задаче выполнимости булевых формул, которая заключается в следующем: можно ли назначить всем переменным, встречающимся в формуле, значения ложь и истина так, чтобы формула стала истинной. Эту задачу относят к разряду NP. Деолаликар утверждает, что нет такой программы, которая может с самого начала быстро выполнить такой подсчет, и поэтому этой проблеме нельзя придать статус P.
Таким образом, задачи разрядов P и NP не идентичны, поэтому на способности компьютеров накладываются серьезные ограничения: многие задачи останутся фундаментально сложными без возможности их облегчения. Для некоторых проблем, включая разложение числа на множители, полученный Деолаликаром результат не дает однозначного ответа, могут ли они быть решены быстро. Но значительный массив задач, называемый NP-завершенные, окажется под угрозой. Известным примером является задача про коммивояжера, которому нужно найти кратчайший маршрут через набор городов. Такие задачи имеют быстрое решение, но если P не равно NP, тогда нет такой компьютерной программы, которая может быстро их решить.
Свои соображения Деолаликар представил на всеобщее обозрение в интернете, пишет британская газета The Daily Telegraph.
Похожие новости:

Ещё один российский математик может получить $1 млн
Одну из так называемых задач тысячелетия, объявленных американским Институтом Клэя, решил россиянин Григорий Перельман, за что ему была присуждена премия размером в миллион...
Ещё один российский математик может получить $1 млн
Математик Перельман объяснил свой отказ от миллиона
Знаменитый на весь мир петербургский математик Григорий Перельман окончательно отказался от миллиона долларов. Премия американского Математического института имени Клэя за...
Математик Перельман объяснил свой отказ от миллиона
Григорий Перельман поставил в тупик иностранных ученых
Российский математик Григорий Перельман "думает над тем, чтобы принять премию", присужденную ему американским Математическим институтом Клэя за доказательство гипотезы...
Григорий Перельман поставил в тупик иностранных ученых
Математику Перельману присуждена Премия тысячелетия
Российский математик Григорий Перельман стал лауреатом премии Математического института Клэя (штат Массачусетс) за доказательство гипотезы Пуанкаре, говорится в сообщении...
Математику Перельману присуждена Премия тысячелетия
Бактерии умеют решать математические задачи
В Journal of Biological Engineering опубликовано исследование, согласно которому «живой» компьютер из бактерий E. coli, способен решать сложные математические задачи...
Бактерии умеют решать математические задачи
Комментариев пока еще нет
Комментировать

События в мире
На правах рекламы