Блог пользователя Edvard

P != NP
Автор Edvard, 14 лет назад, По-русски
Неужели наконец-то доказано? 11 августа на сайте компании HP появился препринт доказательства индийского математика Винай Деолаликар. Если кому-нибудь известно что-нибудь больше чем пишут в новостях то отпишитесь.
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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


См. http://rjlipton.wordpress.com/2010/08/11/deolalikar-responds-to-issues-about-his-p≠np-proof/, http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/.

→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну тогда можно попробовать самому найти ошибку в доказательстве)) Я уже скачал доказательство. Может это поможет привести собственное доказательство))
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится
      Я думаю там нереально разобраться.
      → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да, Эдик, это будет посложнее задачи Inverse-MST, и раз так в 1000 :)
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Время будет можно попробовать)) Я думаю там проблемы могут возникнуть только с переводом на русский))))))))
        → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
За развитием событий можно следить еще здесь: http://michaelnielsen.org/polymath1/index.php?title=Deolalikar's_P!%3DNP_paper 
Ее своевременно дополняют и там описаны основные возможные проблемы с доказательством и линки на блоги разных теоретиков с обсуждением.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Ух, это событие - опубликование доказательства - всколыхнуло интерес к математике. Интересно, что, кроме внимания прессы и других не-математиков, обсуждение доказательства собрало "за одним столом" много специалистов по теории сложности и другим дисциплинам, что является уникальной ситуацией (см. сообщения Terence Tao в блоге rjlipton).

Я и сам попал под влияние, - зачитался всякими научно-популярными статьями о великих задачах XX века, об их решениях и неудачах... Интернет классен тем, что за ~0 минут ты можешь отыскать множество занимательных статей, написанных понятным языком, и ∞ количество ссылок на другие статьи, с каждым разом всё больше отдаляющиеся от первоначальной темы, но всё более и более интересные...

→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да я и сам заинтересовался. Надеюсь доказательство будет неверным и тогда у меня будет возможность сделать это(как и у всех желающих).
    → Ответить
14 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
Мне нравится читать вот такие интересные статейки, хоть я и многое вообще не понимаю :D
Очень интересно было читать про доказательство Теоремы Ферма.
Как её больше 7 лет доказывал один великий математик ... Как на грани провала, он всё таки смог её доказать .. =) Читал целую ночь не отрываясь :) Благо на русском всё :))
Доказательство занимает больше 200 страниц :)
А сам Ферма писал, что он нашёл очень простое доказательство, понятное даже ребёнку, но ему не хватало чуть чуть места что бы написать на маленьком листочке бумажки :) Интересно, можно в будущем появится это доказательство, я верю что оно существует ^_^ !!
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Мне кажется, что вероятность того, что Ферма знал простое доказательство, примерно такая же, как у факта, что P = NP.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится -10 Проголосовать: не нравится
      Мне кажется вы ошибаетесь ... Вероятность очень большая, сейчас нету таких глубоких математиков как Ферма, Гаусс и т.к.. Сейчас всё по другому ... Ферма знал простое решение, он просто слова не бросает на ветер ... подождём ещё пару десятков лет, и увидем что из этого выйдет :)))
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится +2 Проголосовать: не нравится
        да, Ферма еще тот тролль))
        → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится +7 Проголосовать: не нравится
        Вы как будто бы лично ферма знали
        → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Не соглашусь. Скорее всего, Ферма не знал решения. Осмелюсь заметить, что многие "глубокие" математики также бились над этой теоремой, тот же Гаусс (и Эйлер!). На уровне элементарной математики доказательство найти вряд ли удастся, во всяком случае простое, которое якобы было известно самому Ферма. Думаю, что за почти четыреста лет отсутствие простого доказательства было установлено полным перебором букв и слов ;)
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится +4 Проголосовать: не нравится
          Недооцениваешь количество слов :)
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Недооцениваешь количество пытавшихся =)
            Особенно после, того как за доказательство стали обещать премии
            → Ответить
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Тем не менее:
              пусть в статьях бывает 10000 слов. Пусть в простом доказательстве 30 слов. Тогда надо перебрать 1e120 вариантов. Пусть все человечество перебирает 1 вариант в секунду. Получаем 5e102 лет перебора...
              → Ответить
              • 14 лет назад, # ^ |
                  Проголосовать: нравится +8 Проголосовать: не нравится
                Недооцениваешь человеческий разум он сразу отсечёт 1e120 - 10 вариантов. А на оставшиеся 10 вариантов потратит 100 лет.
                → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Думаю что простого доказательства нет. Дело в том что доподлинно известно что у Ферма уже были ошибочные доказательства и утверждения. Ну и как правильно здесь говорили уже почти 400 лет математики не могут его найти...
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          нашли ж
          → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Может не такое уж и простое, но мне кажется доказательство не единственное, так как если вы читали доказательство поймёте о чём я ;))

          Уайлс, Эндрю Джон - великий человек доказавший Великую Теорему Ферма ;) Надеюсь найдутся ещё люди которые не побоятся потратить время и на другие интересные доказательства :))

          ОЙ, что то со шрифтом =_=
          → Ответить