Open tender for P vs NP

[piggymouse]

Ежели кто не читает Twitter/FrF: на getacoder.com разыскивают решателя P vs NP за тоннубаксов. Via blacklion.

Большая часть бидов заставляет меня испытывать глубокий стыд — ведь и я, и многие глубокоуважаемые коллеги часто бываем на месте Адила Хуршида из Исламабада.

Comments

[ygam.livejournal.com]

Это открытая задача, над которой математики бьются уже почти 40 лет.

[dair-spb.livejournal.com]

Я старался понять, в чём, собственно, задача.
Понял, что в полиномиальном времени.

[ygam.livejournal.com]

Ну, в одном ЖЖ-комменте я не смогу изложить теорию вычислительной сложности. Есть класс математических задач, для которых нет алгоритма, решающего их за полиномиальное время. В начале 1970х годов несколько математиков доказали, что если такой алгоритм появится для одной из них, он появится для всех; с тех пор о все новых задачах доказывали, что они принадлежат к этому классу; сейчас известны тысячи таких задач. С тех пор никто не смог ни найти алгоритм для одной из этих задач, ни доказать, что такого алгоритма не существует, ни доказать, что утверждение, что такого алгоритма не существует, недоказуемо. В запросе на этом сайте требуется найти полиномиальный алгоритм для одной из таких задач.

[dair-spb.livejournal.com]

> Есть класс математических задач, для которых нет алгоритма, решающего их за полиномиальное время
Это было понятно.

> если такой алгоритм появится для одной из них, он появится для всех
О! Вот это ново. Хотя вполне понятно.

> С тех пор никто не смог ни найти алгоритм для одной из этих задач, ни доказать, что такого алгоритма не существует, ни доказать, что утверждение, что такого алгоритма не существует, недоказуемо.
А, так вот в чём задача.

Спасибо большое, в голове многое прояснилось.

[ygam.livejournal.com]

О! Вот это ново

Теорема Кука-Левина