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

  • о фальшивой медицине

    Статья о фальшивых исследованиях в медицине. How many studies are faked or flawed? Редактор медицинского журнала "Анестезия" решил специально…

  • как движутся глаза

    Недавно увидел движение глаз на MRI, и с тех пор все время вспоминаю это видео. В монографии о движении глаз, которую я читаю, в самом начале…

  • если ползешь - ползи

    Рожденный ползать, говорили они. Летать не может, говорили они. Прошло 300 миллионов лет, ну и где вы все, летуны? (за картинку спасибо…

  • 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

  • о фальшивой медицине

    Статья о фальшивых исследованиях в медицине. How many studies are faked or flawed? Редактор медицинского журнала "Анестезия" решил специально…

  • как движутся глаза

    Недавно увидел движение глаз на MRI, и с тех пор все время вспоминаю это видео. В монографии о движении глаз, которую я читаю, в самом начале…

  • если ползешь - ползи

    Рожденный ползать, говорили они. Летать не может, говорили они. Прошло 300 миллионов лет, ну и где вы все, летуны? (за картинку спасибо…