Индийский Перельман «съел» Кука

«Проблема Кука» в 1 миллион долларов Индийский математик Виней Деолаликар, работающий в Калифорнии в исследовательском отделе компании «Хьюллет-Паккард», утверждает, что ему удалось найти решение еще одной «задачи тысячелетия», известной как «проблема P и NP». Она относится к одной из важнейших нерешенных вопросов компьютерной науки. Результат своих научных изысканий Деолаликар разместил в Интернете. Напомним, что в последний раз другую «задачу тысячелетия» подобной сложности решил небезызвестный Григорий Перельман. Он первым в мире доказал гипотезу Пуанкаре. И первым в истории отказался от награды за проделанную работу в сумме один миллион долларов США. Вообще же таких глобальных головоломных математических задач несколько. Их выбрали еще десять лет назад эксперты Математического института имени человека, который его основал - миллиардера Лэндона Клея (Landon T. Clay). Находится он в Кембридже (США). И за решение каждой обещано по миллиону долларов. Список получил название Millennium Prize Problems. В перечень входят задачи, название которые простому смертному абсолютно ничего не скажут, а для яйцеголовых они звучат, как священные заклинания: «Гипотеза Римана», «Гипотеза Берча и Свиннертон-Дайера», «Гипотеза Ходжа», «Уравнения Навье - Стокса», «Уравнения Янга - Миллса». И еще есть «Проблема Кука». Ее-то индийский математик Виней Деолаликар и решил. Во всяком случае, он сами в этом уверяет. Но экспертам еще предстоит оценить его решение. «Проблему Кука» еще называют «проблемой P и NP». Под классом P подразумеваются задачи, которые могут быть быстро решены компьютером, под классом NP - задачи, требующие настолько сложных вычислений, что это не по силам ныне существующим компьютерам. Решение «проблемы P и NP» могло бы революционным образом изменить как минимум - основы криптографии, используемой при передаче и хранении данных. И как максимум - повлиять на создание компьютерных программ, а также на скорость работы вычислительной техники, сообщает The New Scientist. Вот образная суть проблемы, сформулированной еще в 1971 году. Допустим, находясь в большой компании, вы хотите убедиться, что там же находится ваш знакомый. Если вам скажут, что он сидит в углу, то вам достаточно доли секунды, чтобы, бросив взгляд, убедиться в истинности информации. В отсутствии этой информации вы будете вынуждены обойти всю комнату, рассматривая гостей. Точно так же, если кто-то сообщит вам, что число 13717421 можно представить, как произведение двух меньших чисел, непросто быстро убедиться в истинности информации, но если вам сообщат, что исходное число можно разложить на множители 3607 и 3803, то это утверждение легко проверяется с помощью калькулятора. Это примеры иллюстрируют общее явление: решение какой-либо задачи часто занимает больше времени, чем проверка правильности решения. Стивен Кук сформулировал проблему: может ли проверка правильности решения задачи быть более длительной, чем само получение решения, независимо от алгоритма проверки. Скептики сомневаются Чтобы легче понять проблему, Математический институт Клэя приводит такой пример: вы должны разместить 400 студентов в 100 аудиториях. Декан снабдил вас списком, в котором перечислены пары студентов, не подходящих друг другу, и велел сделать так, чтобы ни в одной из аудиторий ни один студент не встретил ни одного другого студента, с которым находится в неприязненных отношениях. Это и есть образец проблемы NP: легко проверить, будет ли составленная в результате разбивка на 100 аудиторий с именами студентов в них удовлетворять требованиям декана. Но задача по составлению такой разбивки, которая бы действительно устроила декана, практически нерешаема. Общее количество операций, которые нужно произвести, чтобы оптимально заполнить 100 аудиторий студентами, превышает количество атомов в известной части Вселенной. Таким образом, невозможно построить такой суперкомпьютер, который сможет решить проблему «грубой силой» или простым перебором вариантов - всех комбинаций из 100 аудиторий со студентами. Кроме того, на предположении неравенства P и NP держится большое количество существующих ныне систем защиты информации, от пароля к «аське» до PIN-кода банковской карты. Кроме того, речь идет о задачах, которые оперируют большими массивами данных: имен, адресов, телефонов и т.п. - и решаются при помощи компьютерной техники. Ведь P - это класс задач, решение которых относительно легко найти: например, расположить в алфавитном порядке имена, положим, тысячи человек, найти, кто из них живет в одном городе, на одной улице, составить возрастную картину списка. А вот класс NP включает такие задачи, для которых легко проверить, является ли предлагаемое решение верным. Например, у вас есть код, вы не знаете алгоритма кодирования, но можете легко проверить, какие комбинации не являются (или наоборот, являются) правильным кодом. Таким образом, уточняют специалисты, вопрос, который еще в прошлом веке поставили перед собой математики, следующий: правда ли что задачи, которые просто проверить, в принципе, можно и легко решить? Или, правда ли, например, что компьютер – пусть, положим, только в будущем – можно будет научить легко взламывать коды. Ответ «да» означал бы, что существует универсальное решение множества задач, с которыми раньше не мог справиться компьютер: и это не только щекотливые вопросы криптографии – что, понятно, далеко не всех может порадовать, – но и масса очень полезных задач, оптимизация международных перевозок, например. И вот сегодня математик Деолаликар дает ответ «нет», утверждая, что «Р не равно NP». Однако, пока эксперты скептически относятся к заявлению Деолаликара. У них нет уверенности в том, что институт признает правильным предложенное индийским математиком решение «проблемы P и NP». И в этом пока отличие российского Перельмана от индийского. Наш сам отказался от миллиона, а не нашему - его (миллион) даже не предложат. Хотя профессор Массачусетского института технологии Скотт Ааронсон пообещал заплатить Деолаликару 200 000 долларов, если Институт Клэя утвердит его открытие. Профессор Ааронсон написал, что еле наскребет эту сумму, но пояснил: «Если проблема неравенства P и NP действительно решена, моя жизнь претерпит такой крутой поворот, что выплата двухсот тысяч долларов будет лишь самым незначительным событием в ней». Кстати, а вы знаете, чтобы заставить вас купить ненужную вещь, производители будут сканировать наш мозг ? Читайте об этом в нашем блоге «Толкователи сновидений» и пишите о том, что вам снится - мы растолкуем!

Индийский Перельман «съел» Кука

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