piggymouse

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