ОРЕАНДА-НОВОСТИ. Индийский математик Виней Деолаликар, работающий в Калифорнии в исследовательском отделе компании "Хьюллет-Паккард", утверждает, что ему удалось найти решение ещё одной "задачи тысячелетия", известной как "проблема P и NP". Она относится к одной из важнейших нерешённых вопросов компьютерной науки. Результат своих научных изысканий Деолаликар разместил  в Интернете.

Напомним, что в последний раз другую "задачу тысячелетия" подобной сложности решил небезызвестный Григорий Перельман. Он первым в мире доказал гипотезу Пуанкаре. И первым в истории отказался от награды за проделанную работу в сумме 1 млн долларов США.

Вообще же таких глобальных головоломных математических задач несколько. Их выбрали ещё десять лет назад эксперты Математического института имени человека, который его основал - миллиардера Лэндона Клея (Landon T. Clay). Находится он в Кембридже (США). И за решение каждой обещано по миллиону долларов. Список получил название Millennium Prize Problems. В перечень входят задачи, название которые простому смертному абсолютно ничего не скажут, а для учёных они звучат, как священные заклинания: "Гипотеза Римана",  "Гипотеза Берча и Свиннертон-Дайера", "Гипотеза Ходжа",  "Уравнения Навье - Стокса", "Уравнения Янга - Миллса".  И ещё есть "Проблема Кука". Её-то индийский математик Виней Деолаликар и решил. Во всяком случае, он сами в этом уверяет. Но экспертам ещё предстоит оценить его решение, пишет Комсомольская правда.

"Проблему Кука" ещё называют "проблемой P и NP". Под классом P подразумеваются задачи, которые могут быть быстро решены компьютером, под классом NP - задачи, требующие настолько сложных вычислений, что это не по силам ныне существующим компьютерам. Решение "проблемы P и NP" могло бы революционным образом изменить как минимум - основы криптографии, используемой при передаче и хранении данных. И как максимум - повлиять на создание компьютерных программ, а также на скорость работы вычислительной техники. Вот образная суть проблемы, сформулированной ещё в 1971 году. Допустим, находясь в большой компании, вы хотите убедиться, что там же находится ваш знакомый. Если вам скажут, что он сидит в углу, то вам достаточно доли секунды, чтобы, бросив взгляд, убедиться в истинности информации. В отсутствии этой информации вы будете вынуждены обойти всю комнату, рассматривая гостей.

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

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

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

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

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

Кроме того, на предположении неравенства P и NP держится большое количество существующих ныне систем защиты информации, от пароля к "аське" до PIN-кода банковской карты. Кроме того, речь идёт о задачах, которые оперируют большими массивами данных: имён, адресов, телефонов и т.п. - и решаются при помощи компьютерной техники. Ведь P - это класс задач, решение которых относительно легко найти: например, расположить в алфавитном порядке имена, положим, тысячи человек, найти, кто из них живет в одном городе, на одной улице, составить возрастную картину списка.

А вот класс NP включает такие задачи, для которых легко проверить, является ли предлагаемое решение верным. Например, у вас есть код, вы не знаете алгоритма кодирования, но можете легко проверить, какие комбинации не являются (или наоборот, являются) правильным кодом.

Таким образом, уточняют специалисты, вопрос, который ещё в прошлом веке поставили перед собой математики, следующий: правда ли что задачи, которые просто проверить, в принципе, можно и легко решить? Или, правда ли, например, что компьютер – пусть, положим, только в будущем – можно будет научить легко взламывать коды.

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

И вот сегодня математик Деолаликар даёт ответ "нет", утверждая, что "Р не равно NP".

Однако, пока эксперты скептически относятся к заявлению Деолаликара. У них нет уверенности в том, что институт признает правильным предложенное индийским математиком решение "проблемы P и NP".

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

Следующую сводку НОВИНКИ ТЕХНОЛОГИЙ читайте в пятницу, 13 июля 2010 года в 21.00.

Читайте также:

Цель - Павловская опытная станция

Россияне вспомнили об отдыхе

ФИНАНСОВАЯ СВОДКА на 13.00: ВВП РФ вырос меньше, чем ожидалось

Дорогое Сколково

---------

Информация: ООО "Авто Импэкс Груп" - это лидер продаж автозапчастей оптом для иномарок на российском рынке. Большой ассортимент и наличие на складе принадлежностей для японских, европейских, американских и корейских автомобилей. Бесплатная доставка от 12000 рублей. Внимательное отношение к клиентам. Телефон: (495) 661-9133