P = NP: Какие методы наиболее перспективны? - PullRequest
8 голосов
/ 25 мая 2010

Я знаю, что P = NP до сих пор не решена, но кто-нибудь может рассказать мне кое-что о следующем: Какие в настоящее время наиболее многообещающие математические / компьютерные научные методы, которые могут быть полезными для решения Эта проблема? Или до сих пор нет таких методов, которые могут быть потенциально полезны до сих пор? Есть ли (бесплатный) сборник по этой теме, где я могу найти все / большую часть исследований, проведенных в этой области?

1 Ответ

7 голосов
/ 26 мая 2010

Отличный обзор появился в прошлом году в Коммуникациях ACM. Я думаю, что она стала самой скачиваемой статьей CACM за всю историю, поэтому ваш вопрос может оказаться актуальным: -)

Состояние проблемы P = NP , Лэнс Фортнау, сообщения ACM, Vol. 52 № 9, 2009

...