Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Status report

Введение в суть происходящего в трёх словах: //www.ugcs.caltech.edu/~stansife/pnp.html
Страница, где сообщество общими усилиями анализирует доказательство: //p-is-not-np.tk

Результаты экспертного сообщества по анализу (P ≠ NP)-доказательству Деолаликара на данный момент по мнению Ричарда Липтона написал Терри Тао:
“I think there are several levels to the basic question “Is the proof correct?”:
  1. Does Deolalikar’s proof, after only minor changes, give a proof that P != NP?

  2. Does Deolalikar’s proof, after major changes, give a proof that P != NP?

  3. Does the general proof strategy of Deolalikar (exploiting independence properties in random k-SAT or similar structures) have any hope at all of establishing non-trivial complexity separation results?
After all the collective efforts seen here and elsewhere, it now appears (though it is perhaps still not absolutely definitive) that the answer to #1 is “No” (as seen for instance in the issues documented in the wiki), and the best answer to #2 we currently have is “Probably not, unless substantial new ideas are added”. But I think the question #3 is still not completely resolved, and still worth pursuing (though not at the hectic internet speed of the last few days).”
Subscribe

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…

  • 36

    Традиционный деньрожденный пост. Год выдался необычный. :)

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    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.
  • 0 comments