9 August 2010

Опубликовано доказательство P ≠ NP?

Algorithms
Vinay Deolalikar разослал некоторым ученым свое доказательство, что класс сложности P ≠ NP.

Само доказательство на ~100 страницах.

Можно почитать более или менее адекватный комментарий на ycombinator.

Добавить нечего, читаем и/или ждем мнений специалистов в этой области.

P.S. На всякий случай, ссылка о том, что такое NP и P. (спасибо, SMiX)
Tags:PNPдоказательство
Hubs: Algorithms
+277
20.5k 64
Comments 127
Top of the last 24 hours