Возможно, решена одна из математических "задач тысячелетия"
11 августа 2010 года, 14:45 |Текст: Дмитрий Сафин
Сотрудник Исследовательской лаборатории Hewlett-Packard в Пало-Альто Винэй Деолаликар (Vinay Deolalikar) опубликовал доказательство того, что классы задач P и NP неравны.
Стивен Артур Кук, профессор Торонтского университета, лауреат премии Тьюринга.
Вопросо равенстве классов сложности P и NP, поставленный около 40 лет назад,занимает центральное место в теоретической информатике. За его решение Математический институт Клэя, включивший проблему в список семи «задач тысячелетия»,готов выплатить миллион долларов. Формальное описание этой проблемы,данное одним из её «авторов», известным американским учёным Стивеном Артуром Куком, можно найти здесь.
Предельно упрощённое описание классов P и NP выглядит так: P —это вычислительные задачи, которые легко решаются, а NP — те задачи,решение которых легко проверяется. Примером первого класса задач служит сортировка списка фамилий по алфавиту: очевидно, расположить в нужном порядке даже очень большое число элементов списка несложно. NP-задачи можно сравнить с пазлом, поскольку собрать его трудно, а проверка качества сборки занимает лишь пару секунд.
Известно, что стойкость некоторых популярных алгоритмов шифрования основывается на предположении о сложности задачи факторизации(разложения натурального числа на простые множители). Подтверждение равенства P = NP будет означать, что эти криптографические системы уязвимы.
Решить вопрос о соотношении P и NP пытались многие. Существуют«доказательства» и для P = NP, и для P ≠ NP; хронология их появления и публикации опровержений приведена на этой странице.
Проверка работы г-на Деолаликара, занимающей 107 страниц и лаконично озаглавленной «P ≠ NP», пока только начинается.
«Такой подход к решению нам ещё не встречался, — комментирует сотрудник Технологического института Джорджии Ричард Липтон (Richard Lipton). — Конечно, говорить о том, что он работает, ещё слишком рано, но утверждать обратное я совершенно точно не буду». Некоторые специалисты, впрочем, относятся к доказательству скептически; так, теоретик из Массачусетского технологического института Скотт Ааронсон (Scott Aaronson) в своём блоге пообещал лично увеличить сумму премии на 200 тысяч долларов, если Винэй Деолаликар её всё-таки получит.
Подготовлено по материалам Nature News.
http://science.compulenta.ru/553934/
Сотрудник Исследовательской лаборатории Hewlett-Packard в Пало-Альто Винэй Деолаликар (Vinay Deolalikar) опубликовал доказательство того, что классы задач P и NP неравны.
Стивен Артур Кук, профессор Торонтского университета, лауреат премии Тьюринга.
Вопросо равенстве классов сложности P и NP, поставленный около 40 лет назад,занимает центральное место в теоретической информатике. За его решение Математический институт Клэя, включивший проблему в список семи «задач тысячелетия»,готов выплатить миллион долларов. Формальное описание этой проблемы,данное одним из её «авторов», известным американским учёным Стивеном Артуром Куком, можно найти здесь.
Предельно упрощённое описание классов P и NP выглядит так: P —это вычислительные задачи, которые легко решаются, а NP — те задачи,решение которых легко проверяется. Примером первого класса задач служит сортировка списка фамилий по алфавиту: очевидно, расположить в нужном порядке даже очень большое число элементов списка несложно. NP-задачи можно сравнить с пазлом, поскольку собрать его трудно, а проверка качества сборки занимает лишь пару секунд.
Известно, что стойкость некоторых популярных алгоритмов шифрования основывается на предположении о сложности задачи факторизации(разложения натурального числа на простые множители). Подтверждение равенства P = NP будет означать, что эти криптографические системы уязвимы.
Решить вопрос о соотношении P и NP пытались многие. Существуют«доказательства» и для P = NP, и для P ≠ NP; хронология их появления и публикации опровержений приведена на этой странице.
Проверка работы г-на Деолаликара, занимающей 107 страниц и лаконично озаглавленной «P ≠ NP», пока только начинается.
«Такой подход к решению нам ещё не встречался, — комментирует сотрудник Технологического института Джорджии Ричард Липтон (Richard Lipton). — Конечно, говорить о том, что он работает, ещё слишком рано, но утверждать обратное я совершенно точно не буду». Некоторые специалисты, впрочем, относятся к доказательству скептически; так, теоретик из Массачусетского технологического института Скотт Ааронсон (Scott Aaronson) в своём блоге пообещал лично увеличить сумму премии на 200 тысяч долларов, если Винэй Деолаликар её всё-таки получит.
Подготовлено по материалам Nature News.
http://science.compulenta.ru/553934/