Теория сложности: P vs NP. Основные достижения на 2014 год.

[tdoex]

Одна из центральных задач теории сложности - проблема равенства этих двух классов. К сожалению, я не смог найти русскоязычную литературу, в которой достаточно содержательно описываются результаты в теории сложности, полученные позже 1980-х годов. Определение классов P, NP, NP-complete, теорема Кука-Левина, строгая формулировка проблемы равенства классов P и NP - это ещё есть в книгах Гэри и Джонсона "Вычислительные машины и труднорешаемые задачи", Ахо, Хопкрофта и Ульмана "Построение и анализ вычислительных алгоритмов". Ещё можно найти кое-что о вычислениях с оракулом. Но вот с теоремой Baker-Gill-Solovay о релятивизации, результатами Разборова и Rudich о естественных доказательствах (natural proofs), теоремой Aaronson-Wigderson об алгебраизации возникают проблемы. В связи с этим я прошу помощи по следующим пунктам:

1. Какие основные результаты в теории сложности были получены с момента постановки задачи равенства классов P и NP в 1971 году и до сегодняшнего момента? Желательно общими усилиями составить список из ключевых работ, краткого описания результатов каждой из работ, ссылок на оригиналы и русскоязычные источники, в которых данная работа нашла отражение. Какие ещё значительные результаты были получены помимо работ Baker-Gill-Solovay, Razborov-Rudich, Aaronson-Wigderson?
   
2. В частности, о чём говорится в вышеприведённых трёх работах о релятивицации, алгебраизации и естественных доказательствах? Насколько я понял, в этих работах утверждается, что невозможно решить проблему P vs NP, используя все известные в теории сложности стандартные "приёмы" доказательств. А именно, выделяют два класса таких приёмов: релятивицация и естественные доказательства. Релятивизация связана с добавлением ко всем машинам Тьюринга какого-либо оракула и рассмотрением сложности алгоритмов в предположении, что обращение к оракулу занимает одну операцию. Частный случай релятивицации - "диагонализация". Более общий случай релятивизации - алгебраизация. А естественные доказательства как-то связаны со схемной сложностью. Буду очень благодарен, если кто-нибудь поможет разобраться, что из себя представляют естественные доказательства и доказательства, основанные на диагонализации, релятивизации, алгебраизации. Есть ли вообще строгие определения таких доказательств?

[Xaositect]

Русскоязычной литературы нет. Учите английский, читать математику по-английски проще, чем художественную литературу. Для начала Arora, Barak "Computational Complexity: A modern approach", это недавно вышедший учебник, там разбирается релятивизация, натуральные доказательства, PCP-теорема.

[Sender]

Ну не то чтобы совсем нет. Вот, к примеру, неплохие слайды лекций по теории сложности:http://logic.pdmi.ras.ru/csclub/courses/circuitcomplexityseminar
Там можно найти, в частности, доказательство нижней оценки сложности для монотонных схем, вычисляющих индикатор клики. Да и на список литературы стоит обратить внимание, хоть она сплошь англоязычная.

[Vieux]

Если действительно желаете углубиться в теорию сложность и быть в курсе последних достижений, то придется изучить и читать по-английски. Для начала, посмотрите вот эта работа -http://www.cs.princeton.edu/courses/archive/spr07/cos522/SipserNP.pdf - здесь говорится об истории и статусе проблемы P vs NP. Вы найдете некоторые ответы на ваши вопросы.
А потом, как сказал уважаемый Xaositect, читайте Arora, Barak "Computational Complexity: A modern approach" тут http://www.cs.princeton.edu/theory/index.php/Compbook/Draft или тут http://www.cs.princeton.edu/theory/complexity/book.pdf?q=complexity.

[tdoex]

Спасибо всем! На первое время точно хватит. Жаль, что нет русскоязычной литературы. Это не является серьёзным препятствием, просто читать на английском у меня получается в 2-3 раза медленнее. Особую благодарность хочу выразить Vieux за SipserNP - это именно та работа, в которой относительно подробно (но сжато и лаконично) описывается суть большинства достижений до 2000 года и связь между ними, да ещё и с ссылками на оригиналы.
Буду постепенно разбираться. Возможно, у меня возникнут какие-нибудь вопросы по прочитанному, которые я задам тут. Но вообще, прочитав пару глав, я сделал вывод, что всё необходимое уже есть.

[Vieux]

Можно также следить за новостями в этой области по адресам:
https://complexityzoo.uwaterloo.ca/Complexity_Zoo - Классы сложности и все связанное с ними.
http://www.scottaaronson.com/blog/ - Новости от Скотта Ааронсона.
http://eccc.hpi-web.de/ - Новости, обмен идеями и т.д. в области вычислительной сложности.

[Xaositect]

Также http://blog.computationalcomplexity.org/ , в особенности посты из серии Favorite theorems.

[Vieux]

Есть на русском такие работы автора В. Н. Крупского:
1) Крупский В.Н., Введение в сложность вычислений, 2006;
2) Крупский В.Н., Сложность вычислений - вводный спецкурс 2003,2005;
3) Крупский В.Н., Плиско В.Е. - Теория алгоритмов, 2009.

Они доступны в сети и думаю годятся для ознакомления с предметом.
К сожалению в них нет ничего об основных теоремах и о методах доказательств теории сложности.