Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

о сложности, несколько ссылок

(эта запись может быть интересна людям, интересующимся математикой и информатикой)

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.
Subscribe

  • прогнулись

    Смешно, но не очень :-(

  • талибан и афганское население

    В ситуации развала афганского режима, быстрого наступления талибов и хаоса в Кабуле кажется логичным втиснуть происходящее в привычный шаблон:…

  • принцессы не какают

    Тут израильский спортсмен Артем Долгопят взял золото на олимпиаде (вторая золотая медаль на Олимпиаде за всю историю Израиля), вся страна стоит на…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 19 comments

  • прогнулись

    Смешно, но не очень :-(

  • талибан и афганское население

    В ситуации развала афганского режима, быстрого наступления талибов и хаоса в Кабуле кажется логичным втиснуть происходящее в привычный шаблон:…

  • принцессы не какают

    Тут израильский спортсмен Артем Долгопят взял золото на олимпиаде (вторая золотая медаль на Олимпиаде за всю историю Израиля), вся страна стоит на…