limed's blog

A Solution of the P versus NP Problem
By limed, history, 7 years ago, In English

Thought this would be interesting to many: https://arxiv.org/abs/1708.03486

Norbert Blum

(Submitted on 11 Aug 2017)

Berg and Ulfberg and Amano and Maruoka have used CNF-DNF-approximators to prove exponential lower bounds for the monotone network complexity of the clique function and of Andreevs function. We show that these approximators can be used to prove the same lower bound for their non-monotone network complexity. This implies P not equal NP.
  • Vote: I like it
  • +92
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +64 Vote: I do not like it

I can't say the proof is correct or flawed, but there is a page with lots of proofs that P = NP and that P != NP here if it may be interesting to anyone

→ Reply
»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Really a big new, hope it can pass through the peer review and the author can get Turing Award.

→ Reply
»
7 years ago, # |
  Vote: I like it +53 Vote: I do not like it

I think babin's proof for P != NP is the shortest and the simplest. Here is the complete proof:

Suppose by contradiction that P = NP, then by basic algebra if we reduce P we obtain N = 1 for every N integer which is clearly a contradiction thus the proof is complete.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +57 Vote: I do not like it

    It's wrong if P=0, world rescued

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      babin, what do you say about it?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +104 Vote: I do not like it

        Obviously P!=0 since it stands for Positive :)

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it -12 Vote: I do not like it

          Alternative argument :

          P is a polynomial complexity , if it was 0, it would have been constant( O(1) ), which is not polynomial complexity, therefore P != 0 and the proof is correct, where is my 1kk ?

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
            ← Rev. 2   Vote: I like it +6 Vote: I do not like it

            Actually, at least in some definitions f(x) = 1 is a polynomial of degree 0.

            Also, O(1) is a subset of O(N).

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it +20 Vote: I do not like it

              So many wrong proofs nowadays...

              → Reply
»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

And it's wrong apparently?

→ Reply