Едва только стихли эмоции по поводу отказа российского математика Григория Перельмана от премии в миллион долларов за решение одной из семи задач тысячелетия, как появилось сообщение о решении еще одной из этих задач. На днях в интернете была выложена статья с доказательством важнейшей гипотезы, лежащей в основе всей современной криптографии. Правда, к концу недели специалисты стали сомневаться, что автору работы достанется миллионная премия.
Автор статьи, индийский математик Винай Деолаликар, работает в исследовательском центре Palo Alto компании Hewlett Packard. 11 августа он опубликовал в интернете препринт статьи под названием "P не равно NP". Сама краткость заголовка должна была подчеркнуть значение решаемой проблемы. Задачами класса P в математике называют такие, которые не требуют больших вычислительных затрат на решение. Например, чтобы найти в таблице самое большое число, достаточно один раз просмотреть ее сверху вниз. Задачи класса NP – это такие, где столь же легко проверить, что найденное решение действительно правильное. Например, если нам уже указали максимальное число таблице, этот факт нетрудно проверить. Так что задача поиска максимального числа относится к обоим классам – P и NP.
Вопрос на миллион долларов, который тревожит математиков, состоит в том, есть ли такие задачи, ответ на которые проверить легко, а вот найти его быстро ни за что невозможно? Практика вроде бы подсказывает, что решать задачи обычно труднее, чем проверять. Но математически это еще вовсе не доказано. Между тем, это предположение широко применяется на практике. Например, в криптографии, где очень важно, чтобы взломать шифр было сложно, и на это не хватало бы всех вычислительных ресурсов Земли. Вот почему появление статьи, в которой доказывалось, что классы задач P и NP не совпадают, было воспринято с огромным интересом, и крупнейшие математики немедленно стали проверять доказательство. Мы попросили рассказать о проблеме "P не равно NP" профессора математики Чикагского университета, члена корреспондента Российской академии наук Александра Разборова:
– Это очень простая задача, которую легко объяснить. Это, по существу, философская проблема, сформулированная в математических терминах. Задача, если совсем грубо, состоит в следующем. Предположим, у вас имеется некоторое утверждение, у которого может быть какое-то доказательство, и это доказательство легко проверить – является оно верным или нет. Вопрос состоит в том, можно ли в этой ситуации доказательство быстро найти с помощью компьютера. Понятие доказательства относится не только к математике. Например, можно доказывать, что ваш компьютерный чип или какая-то программа, работают правильно, то есть, грубо говоря, делают то, что им положено делать. Очень большое количество вопросов такого рода оказываются между собой эквивалентными, то есть, если вы можете решить для одной задачи, то можете решить и для другой. И задачи бывают из совсем разных областей.
– Не могли бы вы привести примеры задач, для которых неизвестно, можно ли их решить быстро?
– Пожалуйста, вот задача коммивояжера: у вас имеется N городов, между ними имеются расстояния. Коммивояжер должен их все объездить по одному разу. У вашего коммивояжера есть некоторая смета на дорожные расходы. Существует ли такой путь через все города, что сумма расстояний не превышает эту смету? Если такой путь существует, это и есть то, что я назвал в начале нашей беседы "доказательством". Если вы мне этот путь покажете, то легко подсчитать сумму расстояний и убедиться, что она укладывается в смету. Самое простое, что приходит в голову, это просто перебрать все пути. Но если пунктов несколько десятков, то различных путей будет больше числа атомов во Вселенной. Быстро находить такой путь можно тогда и только тогда, когда можно решить любую другую задачу из списка, который сейчас составляет примерно 10 тысяч задач из совсем разных областей, включая медицины, биологию, химию, все что угодно. Знаменитая проблема, за которую предложен миллион долларов, как раз и состоит в том, всегда ли можно поиск коротких доказательств автоматизировать с помощью компьютера? Вся современная криптография основана на предположении, что P не равно NP. Все, что мы делаем через интернет, все, что мы считаем безопасными операциями, это все основано на данном предположении. Если, предположим, завтра окажется, что P=NP, последствия для мировой экономики будут просто катастрофическими. И в настоящий момент не видно никаких путей к решению этой задачи. Она является очень интересной с математической и, безусловно, с практической точки зрения. По этим причинам институт Клэя и включил ее в список задач тысячелетия.
Доказательство "P не равно NP", опубликованное Винаем Деолаликаром, представляет собой текст на 100 страницах. Сразу после опубликования его стали изучать и проверять ведущие математики мира. Причем, в лучших традициях свободной науки обсуждение открыто ведется в интернете. Неформальным центром дискуссии стал блог профессора Дика Липтона из Технологического института штата Джорджия. И, похоже, дискуссия складывается пока не в пользу автора доказательства. Продолжает Александр Разборов:
– В настоящем случае процедура неформальная. Насколько я понимаю, просто нашлось несколько энтузиастов, ученых высочайшего класса, которые этим заинтересовались и действуют неформально, переписываются с автором, потому что эта статья пока никуда не представлена. Как только статья представлена в журнал, начинается формальная процедура ее рецензирования. Но до этого еще далеко и, опять же, не очевидно, что до этой стадии в данном случае процесс дойдет. В проверке участвуют наиболее солидные ученые. Я думаю, шансы на то, что доказательство правильное, за последние два дня существенно уменьшились. Но, когда происходят такие вещи, даже с неправильным доказательством, обычно дыма без огня не бывает, и что-то полезное и интересное из таких доказательств получают. Но пока делать какие-то заключения рано.
– Представленное доказательство занимает 100 страниц текста. Доказательство Григория Перельмана, который решил несколько лет назад другую проблему тысячелетия, было еще больше. Как проверяются такие большие доказательства. Можно быть уверенным в результате? Это же не теорема Пифагора, которую каждый может проверить сам.
– Здесь есть большая разница между доказательством или даже той областью, которой занимался Гриша Перельман, и этой задачей. Объем страниц здесь значит не так много. Важно, насколько это технически и идейно сложно. Я в любом случае хочу сделать комплимент автору. Совершенно очевидно, что он пытался сделать свое доказательство настолько понятным, насколько возможно. Это большой плюс, и уже даже за это он заслуживает некоторой признательности. Есть математики, которые пишут хорошо, есть математики, которые пишут... по-другому, есть сложные области, есть легкие области. Это 100 страниц гораздо легче прочесть и понять, чем несколько страниц в доказательстве Перельмана, просто потому, что это более простая в некотором смысле область.
– В СМИ сообщалось, что в своем доказательстве Деолаликар использовал методы статистической физики. Разве может основываться на физике доказательство в области чистой математики?
Я не большой специалист в топологии, в доказательстве Перельмана, но в некотором смысле его доказательство тоже основано на физике. Это физическая аналогия, перенесенная в математический мир. Именно этот момент меня совершенно не настораживает. Мы просто не знаем, как решать эту проблему, никаких подходов и идей, как это делать, у нас нет, и поэтому, если выяснится, что здесь используется статистическая физики или что-то еще, я не буду удивлен. В областях ближе к теоретической физике это происходит уже очень давно. Даже в нашей области сложных вычислений все равно есть очень интересный подраздел, который называется "квантовые вычисления", и там идеи теоретической физики используются на каждом шагу. Поэтому я не буду удивлен, и, безусловно, это никак не бросает тень на возможное доказательство.
Итак, похоже, что математическая сенсация середины недели к концу ее несколько померкла. Но это как раз отражает специфику развития научного поиска. Далеко не каждое усилие заканчивается громким успехом, бывают и неудачи, которые становятся трамплином для дальнейших исследований. Интересно было бы проследить, напишут ли СМИ, которые уже сообщили в замечательном доказательстве, что оно поставлено под сомнение научным сообществом.
Автор статьи, индийский математик Винай Деолаликар, работает в исследовательском центре Palo Alto компании Hewlett Packard. 11 августа он опубликовал в интернете препринт статьи под названием "P не равно NP". Сама краткость заголовка должна была подчеркнуть значение решаемой проблемы. Задачами класса P в математике называют такие, которые не требуют больших вычислительных затрат на решение. Например, чтобы найти в таблице самое большое число, достаточно один раз просмотреть ее сверху вниз. Задачи класса NP – это такие, где столь же легко проверить, что найденное решение действительно правильное. Например, если нам уже указали максимальное число таблице, этот факт нетрудно проверить. Так что задача поиска максимального числа относится к обоим классам – P и NP.
Вопрос на миллион долларов, который тревожит математиков, состоит в том, есть ли такие задачи, ответ на которые проверить легко, а вот найти его быстро ни за что невозможно? Практика вроде бы подсказывает, что решать задачи обычно труднее, чем проверять. Но математически это еще вовсе не доказано. Между тем, это предположение широко применяется на практике. Например, в криптографии, где очень важно, чтобы взломать шифр было сложно, и на это не хватало бы всех вычислительных ресурсов Земли. Вот почему появление статьи, в которой доказывалось, что классы задач P и NP не совпадают, было воспринято с огромным интересом, и крупнейшие математики немедленно стали проверять доказательство. Мы попросили рассказать о проблеме "P не равно NP" профессора математики Чикагского университета, члена корреспондента Российской академии наук Александра Разборова:
– Это очень простая задача, которую легко объяснить. Это, по существу, философская проблема, сформулированная в математических терминах. Задача, если совсем грубо, состоит в следующем. Предположим, у вас имеется некоторое утверждение, у которого может быть какое-то доказательство, и это доказательство легко проверить – является оно верным или нет. Вопрос состоит в том, можно ли в этой ситуации доказательство быстро найти с помощью компьютера. Понятие доказательства относится не только к математике. Например, можно доказывать, что ваш компьютерный чип или какая-то программа, работают правильно, то есть, грубо говоря, делают то, что им положено делать. Очень большое количество вопросов такого рода оказываются между собой эквивалентными, то есть, если вы можете решить для одной задачи, то можете решить и для другой. И задачи бывают из совсем разных областей.
– Не могли бы вы привести примеры задач, для которых неизвестно, можно ли их решить быстро?
– Пожалуйста, вот задача коммивояжера: у вас имеется N городов, между ними имеются расстояния. Коммивояжер должен их все объездить по одному разу. У вашего коммивояжера есть некоторая смета на дорожные расходы. Существует ли такой путь через все города, что сумма расстояний не превышает эту смету? Если такой путь существует, это и есть то, что я назвал в начале нашей беседы "доказательством". Если вы мне этот путь покажете, то легко подсчитать сумму расстояний и убедиться, что она укладывается в смету. Самое простое, что приходит в голову, это просто перебрать все пути. Но если пунктов несколько десятков, то различных путей будет больше числа атомов во Вселенной. Быстро находить такой путь можно тогда и только тогда, когда можно решить любую другую задачу из списка, который сейчас составляет примерно 10 тысяч задач из совсем разных областей, включая медицины, биологию, химию, все что угодно. Знаменитая проблема, за которую предложен миллион долларов, как раз и состоит в том, всегда ли можно поиск коротких доказательств автоматизировать с помощью компьютера? Вся современная криптография основана на предположении, что P не равно NP. Все, что мы делаем через интернет, все, что мы считаем безопасными операциями, это все основано на данном предположении. Если, предположим, завтра окажется, что P=NP, последствия для мировой экономики будут просто катастрофическими. И в настоящий момент не видно никаких путей к решению этой задачи. Она является очень интересной с математической и, безусловно, с практической точки зрения. По этим причинам институт Клэя и включил ее в список задач тысячелетия.
Доказательство "P не равно NP", опубликованное Винаем Деолаликаром, представляет собой текст на 100 страницах. Сразу после опубликования его стали изучать и проверять ведущие математики мира. Причем, в лучших традициях свободной науки обсуждение открыто ведется в интернете. Неформальным центром дискуссии стал блог профессора Дика Липтона из Технологического института штата Джорджия. И, похоже, дискуссия складывается пока не в пользу автора доказательства. Продолжает Александр Разборов:
– В настоящем случае процедура неформальная. Насколько я понимаю, просто нашлось несколько энтузиастов, ученых высочайшего класса, которые этим заинтересовались и действуют неформально, переписываются с автором, потому что эта статья пока никуда не представлена. Как только статья представлена в журнал, начинается формальная процедура ее рецензирования. Но до этого еще далеко и, опять же, не очевидно, что до этой стадии в данном случае процесс дойдет. В проверке участвуют наиболее солидные ученые. Я думаю, шансы на то, что доказательство правильное, за последние два дня существенно уменьшились. Но, когда происходят такие вещи, даже с неправильным доказательством, обычно дыма без огня не бывает, и что-то полезное и интересное из таких доказательств получают. Но пока делать какие-то заключения рано.
– Представленное доказательство занимает 100 страниц текста. Доказательство Григория Перельмана, который решил несколько лет назад другую проблему тысячелетия, было еще больше. Как проверяются такие большие доказательства. Можно быть уверенным в результате? Это же не теорема Пифагора, которую каждый может проверить сам.
– Здесь есть большая разница между доказательством или даже той областью, которой занимался Гриша Перельман, и этой задачей. Объем страниц здесь значит не так много. Важно, насколько это технически и идейно сложно. Я в любом случае хочу сделать комплимент автору. Совершенно очевидно, что он пытался сделать свое доказательство настолько понятным, насколько возможно. Это большой плюс, и уже даже за это он заслуживает некоторой признательности. Есть математики, которые пишут хорошо, есть математики, которые пишут... по-другому, есть сложные области, есть легкие области. Это 100 страниц гораздо легче прочесть и понять, чем несколько страниц в доказательстве Перельмана, просто потому, что это более простая в некотором смысле область.
– В СМИ сообщалось, что в своем доказательстве Деолаликар использовал методы статистической физики. Разве может основываться на физике доказательство в области чистой математики?
Я не большой специалист в топологии, в доказательстве Перельмана, но в некотором смысле его доказательство тоже основано на физике. Это физическая аналогия, перенесенная в математический мир. Именно этот момент меня совершенно не настораживает. Мы просто не знаем, как решать эту проблему, никаких подходов и идей, как это делать, у нас нет, и поэтому, если выяснится, что здесь используется статистическая физики или что-то еще, я не буду удивлен. В областях ближе к теоретической физике это происходит уже очень давно. Даже в нашей области сложных вычислений все равно есть очень интересный подраздел, который называется "квантовые вычисления", и там идеи теоретической физики используются на каждом шагу. Поэтому я не буду удивлен, и, безусловно, это никак не бросает тень на возможное доказательство.
Итак, похоже, что математическая сенсация середины недели к концу ее несколько померкла. Но это как раз отражает специфику развития научного поиска. Далеко не каждое усилие заканчивается громким успехом, бывают и неудачи, которые становятся трамплином для дальнейших исследований. Интересно было бы проследить, напишут ли СМИ, которые уже сообщили в замечательном доказательстве, что оно поставлено под сомнение научным сообществом.
