Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

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

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

К сожалению, у меня совершенно нет никакой возможности в ближайшие несколько дней как следует прочитать этот препринт и попытаться проверить доказательства. Я пробежал глазами основные определения и теоремы - выглядит очень интересно и явно не любительские бредни. Если кто-то будет это читать в ближайшее время, расскажите о ваших впечатлениях, пожалуйста. Я постараюсь освободить время для чтения этого препринта ближе к концу рабочей недели или на выходных.
Subscribe

Recent Posts from This Journal

  • этого ещё неоперившегося подонка

    Прекрасная находка bbb ( здесь): историк теории вероятности и статистики Оскар Шейнин и его труд "Чёрная книга: Ошибки и неточности в…

  • следующий раз

    Сегодня в израильских школах был традиционный день памяти убийства Ицхака Рабина. У друга в школе дочери учительница сказала (перевожу с иврита):…

  • компьютер 91 года

    В фейсбуке есть израильское сообщество "в 90-х на этой неделе", там всякие заметки из прессы 90-х, реклама итд. Сегодня попалась реклама компьютера…

  • 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

Recent Posts from This Journal

  • этого ещё неоперившегося подонка

    Прекрасная находка bbb ( здесь): историк теории вероятности и статистики Оскар Шейнин и его труд "Чёрная книга: Ошибки и неточности в…

  • следующий раз

    Сегодня в израильских школах был традиционный день памяти убийства Ицхака Рабина. У друга в школе дочери учительница сказала (перевожу с иврита):…

  • компьютер 91 года

    В фейсбуке есть израильское сообщество "в 90-х на этой неделе", там всякие заметки из прессы 90-х, реклама итд. Сегодня попалась реклама компьютера…