1. Забавная пародия на многочисленные доказательства P?=NP (их, конечно, меньше создают, чем доказательств теоремы Ферма, но тоже хватает).
2. На днях прочитал обзорную статью, которую несомненно рекомендую всем математикам (и близлежащим), кто хочет получить представление о современной теории сложности (complexity theory):
Avi Widgerson, P, NP and Mathematics - a computational complexity perspective (PDF)
Очень хорошее изложение как начал, так и сути главных результатов последних 20 лет примерно (скажем, circuit complexity, the PCP theorem, proof systems итд.)
Если я смогу найти для этого время, мне бы хотелось разобраться во многом из того, о чем рассказывается в этой статье: в частности, в Natural Proofs и в док-ве PCP theorem.
