1. 59
  1. 11

    Can someone smarter than me (i.e. anyone else here) tell me if this is likely to be correct? Maybe even give an understandable-to-a-relatively-educated-layman explanation?

    1. 24

      It’s not written by a crank (the author is actually very well regarded in the field), and it’s an approach that avoids the most obvious pitfalls (relativization, say) which you’d expect, from someone who knows the field. It’s not immediately clear to me how this solution proposes to avoid algebrization, but I’m a certified idiot about this stuff so that may obviously not apply to someone with a better grasp of it.

      Is it likely correct? There’ve been many, many serious attempts over the years, all of which have failed despite the best efforts of those involved. Anything is possible, though, and at the very least we may learn something novel from this attempt.

      1. 4

        I’m unable to find it, but 2 years ago I found a very detailed page discussing a lot of proof attempts and not only evaluating why they failed, but also how they brought science forward. I liked it for the very respectful tone of “yes, it was a flawed attempt, but we learned something”.

        I like that the P vs. NP problem is one of the rare pockets of science where constant public failure is still a reality and good.

        1. 1

          If you look at the discussions on reddit, most people think it’s likely to be a faulty proof, but the guy is credible enough to not dismiss the paper outright.

      2. 7

        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 Andreev’s 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.

        I kinda understand the last sentence I guess.

        1. 12

          AFAICT, that group (Berg, Ufberg, Amano, and Maruoka) proved that those two problems have exponential lower bounds in a special case.

          This new paper claims to prove that the exponential lower bound holds in general, and since all NP problems can be mapped into other NP problems, it implies that all NP problems must have an exponential lower bound.

        2. 4

          As additional context https://www.win.tue.nl/~gwoegi/P-versus-NP.htm:

          This page collects links around papers that try to settle the “P versus NP” question (in either way).

          And later it has a collection of chronological milestones about the problem.

          1. 2

            Aaronson comments on it at the top of this post: http://www.scottaaronson.com/blog/?p=3389

            1. 1

              I think we should consider any proof of P v. NP spam unless there’s a really, really, really good reason to believe it has a shot.

              1. 49

                This one’s sort of interesting mostly in that it comes from a fairly senior researcher in the field, who’s written a computability theory textbook and has reasonably influential publications in the relevant area of research going back 35 years. Doesn’t mean the proof is correct, but it’s at least not the usual quack-proof profile.

                1. 12

                  Works for me; unflagged.

              2. 1
                1. 2

                  Well to be fair, this isn’t overturning any physics, but rather an attempt at proving something we already believe is true (at least in practice; all our cryptography depends on it).

                  1. 3

                    There’s always Merkle puzzles!