Holy fucking shit! (P \neq NP)

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

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

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

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

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



Архив записей в блогах:
В феврале 2007 года весь мир буквально потрясла фотография израильского министра обороны Амира Переца, сделанная во время военных учений на аннексированных Голанских высотах. Достаточно рядовое фото, исполненное Эфраимом Шриром, запечатлевшее новоиспеченного министра обороны, наблюдающего ...
...
В Качинской долине есть место очень популярное среди любителей крымского пешеходного туризма, но спроси у любого крымчанина - что такое Алимова балка - редко кто тебе ответит. Вчера на работе сказал сослуживцам, что в воскресенье ходили в Алимову балку, так от вопросов отбоя не было - а ...
В детстве я обожала читать. Помню случай, когда мама купила мне на день Рождения книгу ярко жёлтого цвета «Королевство Кривых Зеркал» и спрятала подальше. Как я доставала книгу и читала её втихаря, пока дома некого не было. Конечно же, ко дню ...
На этой фотографии запечатлен результат события, произошедшего 1 октября 1938 года, за которое Германия выдавала определенные награды. История так сложилась, что Германия в 30-х несколько раз присоединяла к себе территории, населенные этническими немцами. Поэтому была создана целая ...