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

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

Фото (c)AFP

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

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

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

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

Еще один пример задачи класса сложности NP – это сборка мозаики вслепую. Вы легко можете определить, правильно ли уложены все кусочки, но вот получить, скажем, Мону Лизу из тысячи разноцветных кусочков, перебирая различные их сочетания, уже не так просто.

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

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

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

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

Винай Деолаликар. Фото с сайта hp.com
Винай Деолаликар. Фото с сайта hp.com

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

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

Обсудить
Displaced people from the minority Yazidi sect, fleeing violence from forces loyal to the Islamic State in Sinjar town, walk towards the Syrian border, on the outskirts of Sinjar mountain, near the Syrian border town of Elierbeh of Al-Hasakah Governorate August 11, 2014. Islamic State militants have killed at least 500 members of Iraq's Yazidi ethnic minority during their offensive in the north, Iraq's human rights minister told Reuters on Sunday. The Islamic State, which has declared a caliphate in parts of Iraq and Syria, has prompted tens of thousands of Yazidis and Christians to flee for their lives during their push to within a 30-minute drive of the Kurdish regional capital Arbil. Picture taken August 11, 2014. REUTERS/Rodi Said (IRAQ - Tags: POLITICS CIVIL UNREST TPX IMAGES OF THE DAY) FOR BEST QUALITY IMAGE ALSO SEE: GM1EA8M1B4V01Дважды отверженные
Почему от женщин, вырвавшихся из плена боевиков, отворачивается общество
Participants attend a gay pride parade in central Istanbul June 30, 2013. Tens of thousands of anti-government protesters teamed up with a planned gay pride march in Istanbul. Crowds were stopped by riot police from entering Taksim, the centre of previous protests, but the atmosphere appeared peacefulОпасное интернет-проникновение
Грозит ли подъем геев-мусульман исламскому миру
Китайский интерес
Пекин желает смерти уйгурским боевикам в Сирии, но вмешиваться в войну не готов


Из ЕС в сексуальное рабство
Что вынуждает румынок отправляться на Сицилию, где их ждет неволя
Парное выступление
Министры России и Японии обсудили безопасность в формате «два плюс два»
Пиджак и боб
Самое крутое автомобильное видео марта
Самые необычные ДТП
Автомобили на крышах, в бассейнах и другие непонятные аварии, достойные премии
Уже в воскресенье
Все, что нужно знать перед новым сезоном Формулы-1
Машины, которым не повезло
Посмотрите, какими могли бы быть известные машины
Бог простит
В церкви нашли квартиру с красной мебелью и портретами в стиле поп-арт
Фрэнк ГериСпугнули рыбу
Почему антисемиты изгнали из Канады создателя «танцующего дома»
«Наш дом — колония строгого режима»
История семьи, оказавшейся на грани распада из-за дачи
Цветам не место в доме
Почему дети мешают взрослым жить счастливо в собственных квартирах