Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

P?=NP: возможный новый результат

Появился свежий препринт; один из авторов - известный учёный. В статье содержатся очень сильные утверждения по поводу несуществования формальных доказательств P!=NP (P?=NP - самая знаменитая нерешённая проблема в computer science; если вы ничего о ней не знаете, вряд ли всё остальное в этой записи будет понятно) Авторы утверждают в частности, что не существует формального доказательства P!=NP ни в одном полиномиальном (в смысле времени распознавания аксиом) омега-консистентном расширении PA (Peano Arithmetic). С практической точки зрения, это очень близко к "P!=NP недоказуемо", и если доказательство будет принято... многое в этой научной области изменится.

К сожалению, у меня совершенно нет никакой возможности в ближайшие несколько дней как следует прочитать этот препринт и попытаться проверить доказательства. Я пробежал глазами основные определения и теоремы - выглядит очень интересно и явно не любительские бредни. Если кто-то будет это читать в ближайшее время, расскажите о ваших впечатлениях, пожалуйста. Я постараюсь освободить время для чтения этого препринта ближе к концу рабочей недели или на выходных.
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.
  • 15 comments