Создание, ликвидация, реорганизация ЮЛ и ИП. Быстро, качественно, надежно, без отказов, недорого! Тел. 8482 785225
Тольятти-Новости
   
16+
Система Orphus
АвтоВАЗ Автоновости Автобезопасность Автодилеры Автомойки Автопрокат Автотюнинг Автошколы Новинки сезона Тест-драйвы Объявления
Программы и акции Кредиты Пластиковые карты Вклады Другие услуги
Больницы Салоны красоты Новости Статьи
Новости Автомобиль Интервью Персоны Результаты Расписание гонок Фотоотчеты Видео Партнерам
11.08.10 19:37

Математик из США утверждает, что решил еще одну «задачу тысячелетия»

Версия для печати
www.adobe.com Винай Деолаликар из лаборатории Hewlett-Packard в Пало-Альто в Калифорнии уверен, что доказал известное в информатике утверждение "Р не равно NP". 

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

Последним, кто решил одну из "задач тысячелетия", оказался российский математик Григорий Перельман. Ученый-эксцентрик из Санкт-Петербурга живет затворником и практически не общается с коллегами. Свое доказательство гипотезы Пуанкаре, над которой около ста лет ломали голову лучшие умы мировой математики, он опубликовал в интернете. Когда же Перельману предложили получить премию в миллион долларов, он отказался и даже не приехал на церемонию награждения за символическим призом. 

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

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

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

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

Свои соображения Винай Деолаликар представил на всеобщее обозрение в интернете, пишет британская газета The Daily Telegraph. 

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

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

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

Но на самом деле одна из выдающихся проблем информатики в том, чтобы определить, есть ли такие вопросы, ответы на которые можно быстро проверить, но которые требуют невозможно долгого времени на решение каким-либо непосредственным способом. 

Профессор Массачусетского института технологии Скотт Ааронсон настроен скептически: он взялся заплатить Деолаликару 200 000 долларов, если Институт Клэя утвердит его открытие. Профессор Ааронсон написал, что еле наскребет эту сумму, но пояснил: "Если проблема неравенства P и NP действительно решена, моя жизнь претерпит такой крутой поворот, что выплата двухсот тысяч долларов будет лишь самым незначительным событием в ней", отмечает Newsru.com.



Возврат к списку

Закрыть
Логин:
Пароль:
Забыли свой пароль?
Регистрация
Чтобы оставить комментарий, необходимо авторизоваться
Поделиться: Twitter В контакте Мой мир facebook
Код для блога: Livejournal Livejournal Я.ру Я.ру LiveinternetLivinternet.ru Скопировать код



29.06.2017  Федор Емельяненко отстранен от ринга на три месяца

29.06.2017  Sony планирует возобновить выпуск виниловых пластинок

29.06.2017  Криштиану Роналду срочно возвращается домой из-за рождения детей

29.06.2017  В армии США могут запретить продукты "Лаборатории Касперского"

29.06.2017  Робот R2-D2 из "Звездных войн" продан с аукциона почти за 3 миллиона долларов

28.06.2017  В Донецкой области при подрыве автомобиля погиб полковник СБУ

28.06.2017  Британским болельщикам сделали памятку к поездке на ЧМ-2018 в России

28.06.2017  В Китае спущен на воду первый собственный ракетный крейсер

28.06.2017  Через 10 лет iPhone произведет революцию в восприятии информации

28.06.2017  В США отмечают рост числа пластических операций "под Меланию Трамп"






о серверепартнеры
рекламодателямобратная связь


Все замечания, пожелания и предложения присылайте по адресу. По вопросам размещения рекламы обращайтесь в . Авторские права на дизайн и всю информацию веб-сайта, подбор и расположение материалов принадлежат ФЭР "Альтернатива". Все права защищены и охраняются законом, при использовании материалов сервера гиперссылка на ИС "Тольятти-Новости" обязательна. Свидетельство о регистрации Эл № ФС 77-25259 от 18 августа 2006 года, выдано Федеральной службой по надзору за соблюдением законодательства в сфере массовых коммуникаций и охране культурного наследия.