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

P = NP
Автор Nyatl, 13 лет назад, По-русски

http://www.ime.usp.br/~weiss/peqnp-11-05-30.pdf

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится
Уже проверил что-ли?)

Вот тут полно этих работ:


72 работы. Почти никакие не проверены. Половина говорит, что доказали равенство, другая половина — наоборот.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится
    Редко можно увидеть, когда два сокомандника общаются через блог :)
    → Ответить
13 лет назад, # |
← Rev. 3   Проголосовать: нравится +21 Проголосовать: не нравится
"Proof by contradiction. Assume P=NP. Let y be a proof that P=NP. The proof y can be verified in polynomial time by a competent computer scientist, the existence of which we assert. However, since P=NP, the proof y can be generated in polynomial time by such computer scientists. Since this generation has not yet occurred (despite attempts by such computer scientists to produce a proof), we have a contradiction."
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    It's worth mentioning the preceding collector's (ironical?) comment:
    Hubert Chen has a webpage (2003) with a really short argument that "P-not-equal-to-NP"
    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

    So, it is not a real proof, just a suppose. For example, people use classical multiplication for many years, but more asymptotically optimal algorithm was invented by Karatsuba, as you know, only in XX century.

    UPD. Sorry, if your comment is ironic, and my answer is too serious :)
    → Ответить