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

[luft]

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

Новость о том, что сотрудник лаборатории 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 за полиномиальное время.

[Иван Александрович]

Мимо

Математики окончательно разуверились в решении задачи тысячелетия

Десять дней назад индийский математик Винэй Деолаликар (Vinay Deolalikar) выложил в Cеть статью, в которой, по его утверждению, доказал одно из важнейших неравенств математики - неравенство классов сложности P и NP. Это сообщение вызвало невиданный резонанс среди коллег Деолаликара – ученые забросили свою основную работу и начали массово читать и обсуждать статью. Практически сразу специалисты обнаружили в доказательстве недочеты, а уже через неделю математическое сообщество пришло к выводу, что с поставленной задачей Деолаликар не справился.

Заявка на миллион

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

Коротко проблема неравенства классов сложности P и NP формулируется так: "Если положительный ответ на некий вопрос можно быстро проверить, то верно ли, что можно быстро найти ответ на этот вопрос". Задачи, для которых актуальна эта проблема, относятся к классу сложности NP (задачи класса сложности P можно назвать более простыми – в том смысле, что их решение точно можно найти за разумное время).

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

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

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

[Иван Александрович]

Продолжение.

Но в данном случае автором работы, незамысловато названной "P не равно NP" (прочитать текст можно здесь), был не околонаучный безумец, а работающий ученый, причем работающий в очень уважаемом месте – Исследовательских лабораториях Hewlett-Packard в Пало-Альто. Более того, положительный отзыв на его статью дал один из авторов задачи тысячелетия о неравенстве P и NP, Стивен Кук (Stephen Cook). В сопроводительном письме, которое Кук разослал коллегам вместе со статьей (Кук был одним из нескольких ведущих математиков, кому индиец прислал свою работу для ознакомления), он написал, что работа Деолаликара – это "относительно серьезная заявка на доказательство неравенства классов P и NP".

Неизвестно, то ли рекомендация корифея в области теории сложности (именно эта область математики имеет дело с неравенством P и NP) сыграла свою роль, то ли важность самой задачи, но множество математиков из разных стран отвлеклись от своей основной работы и начали разбираться в выкладках Деолаликара. Люди, знающие о неравенстве классов сложности P и NP, но не занимающиеся этой темой непосредственно, также принимали активное участие в обсуждении. Например, они завалили вопросами о доказательстве специалиста по компьютерным наукам Скотта Ааронсона (Scott Aaronson) из Массачусетского технологического института (MIT).

Ааронсон в момент появления статьи Деолаликара был в отпуске и не мог сходу разобраться в доказательстве. Тем не менее, для того чтобы подчеркнуть его важность, он заявил, что отдаст индийцу 200 тысяч долларов, если математическое сообщество и Институт Клэя признают его верным. За этот экстравагантный поступок многие коллеги осудили Ааронсона, заявив, что истинный ученый должен опираться только на факты, а не эпатировать публику красивыми жестами.

http://lenta.ru/articles/2010/08/18/fail/