Математик из Индии претендует на решение задачи про сравнение классов сложности P и NP
Новость о том, что сотрудник лаборатории 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 за полиномиальное время.
Доказательство Деолаликара занимает 116 страниц. Пока статья индийского математика не опубликована в рецензируемом журнале (хотя, например, статьи Григория Перельмана, за которые институт Клэя присудил ему Премию тысячелетия, так никогда и не были опубликованы), и сам он подчеркивает, что это только предварительный вариант, а окончательная версия появится чуть позже.
Так что формально математики, желающие публично оценить доказательство, должны дождаться выхода готового текста. Но неформально многие из них уже начали изучать статью Деолаликара и некоторые уже выступили с критикой используемого ученым подхода.
А вот сотрудник Массачусетского технологического института (MIT) Скотт Ааронсон (Scott Aaronson) поступил иначе – он пообещал отдать Деолаликару 200 тысяч долларов, если выяснится, что его доказательство верно. Свой поступок Ааронсон мотивировал так: «Если неравенство P и NP действительно будет доказано, то моя жизнь изменится настолько кардинально, что потеря 200 тысяч будет совершенно незначима». К этим словам трудно что-то прибавить.
