Юстас = Алексу?

Математик из Индии претендует на решение задачи тысячелетия

Фото (c)AFP

Новость о том, что сотрудник лаборатории Hewlett-Packard в Пало-Альто индиец Винэй Деолаликар (Vinay Deolalikar) написал статью, в которой сделал вывод, что классы сложности P и NP не равны, появилась в математических блогах еще в начале недели. Авторы и комментаторы этих блогов немедленно окрестили новость “сенсационной” и даже “революционной” и принялись бурно обсуждать детали доказательства и его значение для человечества. Однако официальные СМИ причем, в основном, западные, написали о Деолаликаре только сейчас. Задержка связана с тем, что среди научных журналистов не так много математиков, а без специального образования разобраться в оригинальной статье практически нереально.

В общем-то, от задачи тысячелетия сложно ожидать, что она будет легкой для понимания. Как написано на сайте института Клэя “Приз за решение задач тысячелетия призван отметить некоторые из самых сложных проблем, с которыми математики пытаются справиться на рубеже двух тысячелетий”. Раз уж сотни и даже тысячи математиков не смогли совладать с этими задачами, значит, они действительно неподъемные.

Впрочем, как раз на сайте института Клэя приведено очень доступное описание того, что же на человеческом языке означает фраза “классы сложности P и NP не равны”. Воспользуемся этим объяснением. Предположим, что перед вами стоит задача поселить студентов в общежитие, причем доступных мест всего сто, а желающих поселиться – четыреста. Кроме того, руководство спустило сверху список пар студентов, которых ни в коем случае нельзя селить вместе. Очевидно, что после того, как расселение завершено, вы можете легко проверить, были ли выполнены все условия, но вот справиться с задачей за разумное время чрезвычайно сложно – количество вариантов выбора сотни студентов из четырехсот превышает число атомов во Вселенной.

Такого рода задачи называют задачами класса сложности NP, и их очень сложно решить “в лоб” (то есть перебором всех возможных вариантов) за вменяемое время при помощи любых самых мощных суперкомпьютеров. Однако сам факт того, что задачу, правильный ответ на которую легко проверить (в нашем случае, просто сверившись с полученным от руководства списком), действительно нельзя решить в относительно короткие сроки при помощи, например, какого-нибудь хитрого алгоритма, строго не доказан. На языке математиков отсутствие такого доказательства записывается как знак вопроса в формуле "P = NP?". Как уже догадался читатель, задачи класса сложности P можно решить за адекватное время (ученые используют термин “полиномиальное время”, который означает, что время решения задачи не превосходит полинома от размера данных).

Впервые вопросом о равенстве или неравенстве классов сложности P и NP одновременно задались сразу два математика – Стивен Кук (Stephen Cook) и Леонид Левин в 1971 году. С тех пор ученые безуспешно пытаются на него ответить. Доказательного утверждения, можно ли все-таки поставить знак равенства между P и NP ждут не только исследователи, интересующиеся исключительно фундаментальными аспектами математики (для них вопрос является по-настоящему животрепещущим). Эта задача тысячелетия чрезвычайно важна для специалистов, занимающихся теориями компьютерных вычислений и шифрования данных.

Интерес последних, вообще-то говоря, должен разделять любой человек, который хоть раз платил за какие-то покупки в интернете своей кредитной картой. Когда вы посылаете реквизиты карты на адрес магазина, они отправляются туда в зашифрованном виде, причем чаще всего шифрование производится не по сложным схемам, о которых все мы знаем из книг о шпионах. В современных шифрах используют большие числа – передаваемая информация кодируется огромным количеством цифр (так называемый ключ), и на вскрытие этого кода злоумышленнику придется потратить столько времени, что эта задача потеряет всякий смысл.

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

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

Доказательство Деолаликара занимает 116 страниц (здесь его можно скачать в формате pdf). Пока статья индийского математика не опубликована в рецензируемом журнале (хотя, например, статьи Григория Перельмана, за которые институт Клэя присудил ему Премию тысячелетия, так никогда и не были опубликованы), и сам он подчеркивает, что это только предварительный вариант, а окончательная версия появится чуть позже. Так что формально математики, желающие публично оценить доказательство, должны дождаться выхода готового текста. Но неформально многие из них уже начали изучать статью Деолаликара и некоторые уже выступили с критикой используемого ученым подхода.

А вот сотрудник Массачусетского технологического института (MIT) Скотт Ааронсон (Scott Aaronson) поступил иначе – он пообещал отдать Деолаликару 200 тысяч долларов, если выяснится, что его доказательство верно. Свой поступок Ааронсон мотивировал так: “Если неравенство P и NP действительно будет доказано, то моя жизнь изменится настолько кардинально, что потеря 200 тысяч будет совершенно незначима”. К этим словам трудно что-то прибавить.

Обсудить
Наука и техника00:0117 ноября

Пробила дно

Планета-пришелец расколола Землю и сдвинула континенты
Сулейман КеримовЛазурно: российского миллиардера задержали в Ницце
Сулеймана Керимова подозревают в отмывании миллионов евро
Моя семья
Легендарный маньяк и его культ кровавых убийц держали в страхе всю Америку
Судьба генерала: Ратко Младич умрет в тюрьме
Он убивал мусульман тысячами и не щадил даже детей
Кровавая ривьера
Франция отстреливает врагов по всему миру, пока никто не видит
«Великое прошлое нас развращает»
Почему россияне не принимают себя
«Происходящее — форма женского освобождения»
Йоаким Триер о мистической драме про лесбийскую любовь и Бога
Признак оперы
Как Дмитрий Хворостовский стал главным оперным певцом России
Циркуль в глаз
Судьба еврейского художника: от украинских сказок до нацистской выставки
Что. Вы. Наделали
Как мы потеряли идеальный Porsche и снова его нашли
«Американец», который смог
Самые невероятные версии Chevrolet Corvette, от которых сносит крышу
Мистер Спок
Мы пощупали новейший Aston Martin Vantage и делимся первыми впечатлениями
Из бананов и палок
Что получается, когда машины пытаются делать в Уганде, Кении и других странах
Ловушка для планктона
Тест: Какой офис идеально вам подходит
Это чисто Питер
Сколько стоят квартиры в воспетом Шнуром городе на Неве
Берите две
Пять стран, где ипотеку дают под смешной процент
«Моя бывшая живет на помойке»
Москвич сделал из жены бомжа, и ему не стыдно