о сложности, несколько ссылок
Feb. 17th, 2009 05:31 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avva(эта запись может быть интересна людям, интересующимся математикой и информатикой)
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.
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.
