Open tender for P vs NP

[piggymouse]

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

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

Comments

[tyrex.livejournal.com]

пьер ферма, при том, жжот.

и у тебя autorepy/accept стоит? :-)

[piggymouse.livejournal.com]

Не понял про autoreply.

[tyrex.livejournal.com]

ну, там в основном роботы бидят, шаблонами, нет?.

[piggymouse.livejournal.com]

Ааа, это многое объясняет. Не, я в более метафорическом смысле. По такого рода сайтам никогда не шарился. И пивом в начале девяностых не торговал, позор мне, не знаю я жизни.

[caseq.livejournal.com]

Спасибо, made my day!

[piggymouse.livejournal.com]

А мой-то!

[dair-spb.livejournal.com]

Почитал википедию про эти пэ и энпэ. Не понял.

[ygam.livejournal.com]

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

[dair-spb.livejournal.com]

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

[ygam.livejournal.com]

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

[dair-spb.livejournal.com]

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

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

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

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

[ygam.livejournal.com]

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

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

[old-skipper.livejournal.com]

аааааааа гребаный стыд!
подстолом!

[pbl.livejournal.com]

Самый винрарный VinayDeolalikar, конечно. Впрочем, там какие-то фэйтал флоз, если верить британским джорджийским ученым.

[piggymouse.livejournal.com]

Самый там Ферма.

[pbl.livejournal.com]

а) не согласен; б) вообще боян. деолаликар же совсем свеженький и прямо истекает жырчегом.