Nyatl's blog

P = NP
By Nyatl, 13 years ago, In Russian

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

  • Vote: I like it
  • +1
  • Vote: I do not like it

13 years ago, # |
← Rev. 3   Vote: I like it +21 Vote: I do not like it
"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."
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    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"
    → Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    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 :)
    → Reply