Holy fucking shit! (P \neq NP)

yvl — 08.08.2010 Похоже, мы станем свидетелями огромного прорыва человеческой мысли. По сообществу поползло докзательство разделения классов сложности P и NP. Эта задача является ключевой в теории вычислительных систем и математике вообще и находится в числе задач тысячелетия. По моему мнению она далеко опережает все остальные задачи по их практическим последствиям. Доказательство занимает 102 страницы (с библиографией) и применяет весьма обширный матаппарат.

Если вы в теме, то в зависимости от вашего часового пояса и близости к Столпам вскоре вы получите копию. Вероятно, как только автор получит подтверждения своей правоты (народ не сможет найти лажу), доказательство попадет в свободный доступ. Пока я его в открытом доступе найти не смог.

Стив Кук по поводу этого доказательства сказал "Это кажется сравнительно серьезной заявкой на решение вопроса P vs NP". Будем ждать реакции от сообщества, а пока сами на досуге полистаем.

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

Оставить комментарий

Популярные посты:

• Архив