News for hackers. Stuff that matters.
Re:A Solution of the P versus NP Problem? by lisper on Monday August 14, 2017 @02:51PM (#15011416)
FWIW, my assessment is that this paper passes the Aaronson test, as well as my own personal bogometer. If I were a betting man, my money would be on "the proof will turn out to have a flaw, but it will be hard to find the flaw, and the finding of the flaw will be interesting in and of itself, and possibly even advance the field."
Re:A Solution of the P versus NP Problem? by jl6 on Monday August 14, 2017 @04:29PM (#15012556)
And even though it may be hard to find the flaw, it will be easy to verify that it is a flaw.
Re:A Solution of the P versus NP Problem? by GenerocUsername on Monday August 14, 2017 @06:32PM (#15013629)
If only we had a way to make finding the flaw as easy as verifying the flaw
Re:A Solution of the P versus NP Problem? by Filligree on Monday August 14, 2017 @06:45PM (#15013713)
I don't think it would be possible to make finding it as easy as verifying it, but how can we prove that?
Re:A Solution of the P versus NP Problem? by soberhoff on Monday August 14, 2017 @08:07PM (#15014213)
Finding flaws in proofs is as easy as verifying them. After all, finding a flaw amounts to just checking a proof. Finding a proof is the truly hard challenge.
Re:A Solution of the P versus NP Problem? by evincarofautumn on Monday August 14, 2017 @09:38PM (#15014640)
Checking a proof isn’t necessarily easy, of course, in the sense of both human hardness—such as requiring a lot of background, using dense notation, or being very long—and computational hardness, such as using a logic whose decision procedure takes exponential time.
Re:A Solution of the P versus NP Problem? by soberhoff on Tuesday August 15, 2017 @07:55AM (#15017327)
What kind of esoteric logic yields proofs that require exponential time to check?
Re:A Solution of the P versus NP Problem? by fmap on Tuesday August 15, 2017 @10:37AM (#15018540)
Proof checking in dependent type theory is nonelementary. Of course, this is a completely artificial result with no real world consequences, but that's complexity theory for you...
Re:A Solution of the P versus NP Problem? by soberhoff on Tuesday August 15, 2017 @11:13AM (#15018961)
Well, I'm sure we can all agree that the mathematical paper we're discussing could be formalized into a proof that could be checked in linear time.
Re:A Solution of the P versus NP Problem? by Blaisorblade0 on Wednesday August 16, 2017 @12:21PM (#15028731)
That's only obvious in a vacuous sense.

As a PhD student in Programming Languages, can I request a reference?* Nobody managed to provide one on MathOverflow, and that's the StackExchange for professional mathematicians:

https://mathoverflow.net/q/226966/36016

Of course, your claim is vacuously true, since you can add a trace of all steps of a proof verifier. It's also vacuously true because you can add a dump of the Internet to the proof. Neither thing is insightful.

> what we normally think of as an "honest proof" is a series of steps each of which follows from the previous by application of one of a finite number of axioms or rules of deduction, and such an "honest" proof is thus checkable in linear time by checking each step

Also, for the record: actual formal proofs for (say) standard ZFC are exponentially bigger than anything you want to work with.

EDIT: To clarify, I didn't mean to imply I'm some authority, just to suggest I'm not so obviously* an idiot. Which was maybe stupid anyway.

Re:A Solution of the P versus NP Problem? by soberhoff on Wednesday August 16, 2017 @12:43PM (#15028946)
Well, I've spent a lot of time with theorem provers as well as with normal mathematics. I've never experienced an exponential blowup when formalizing mathematical ideas. It would always boild down to step-by-step verification. And I don't see any reason to suspect that the paper under discussion uses non-standard techniques.
Re:A Solution of the P versus NP Problem? by evincarofautumn on Wednesday August 16, 2017 @03:10PM (#15030246)
Wow, this got more replies than I expected. I was partly kidding, in that I don’t think it’s a huge concern for humans, but for example the tableau decision procedure[1] for modal logics such as epistemic logic is EXPTIME-complete[2].

[1]: https://en.wikipedia.org/wiki/Method_of_analytic_tableaux

[2]: https://arxiv.org/abs/0808.4133

Re:A Solution of the P versus NP Problem? by liberte82 on Monday August 14, 2017 @07:04PM (#15013821)
Someone should research and write a paper about it.
Re:A Solution of the P versus NP Problem? by Halved on Monday August 14, 2017 @08:18PM (#15014281)
But then how will we know that paper is correct?
Re:A Solution of the P versus NP Problem? by KGIII on Monday August 14, 2017 @10:07PM (#15014766)
I'm pretty sure that the answer to that question involves a cat.
Re:A Solution of the P versus NP Problem? by PrunJuice on Monday August 14, 2017 @10:17PM (#15014804)
Sounds hard.
Re:A Solution of the P versus NP Problem? by spinsser on Tuesday August 15, 2017 @01:20AM (#15015722)
no problem
Re:A Solution of the P versus NP Problem? by TimTheTinker on Tuesday August 15, 2017 @01:58AM (#15015877)
NP-hard.

/dodge

Re:A Solution of the P versus NP Problem? by petters on Tuesday August 15, 2017 @04:02AM (#15016330)
That was the joke. :-)
Re:A Solution of the P versus NP Problem? by azeirah on Tuesday August 15, 2017 @04:23AM (#15016406)
This is getting a bit too meta for my tastes :')
Re:A Solution of the P versus NP Problem? by EGreg on Tuesday August 15, 2017 @12:27AM (#15015483)
By using the algorithm!
Re:A Solution of the P versus NP Problem? by manyoso on Tuesday August 15, 2017 @10:56AM (#15018766)
My favorite comment. By far.
Re:A Solution of the P versus NP Problem? by jacquesm on Monday August 14, 2017 @09:22PM (#15014588)
This lines up perfectly with most software bugs. Hard to find, but once you have them easy to prove they are the cause of the problem. The difference is that in software bugs are usually fairly easy to fix, a math proof with a bug in it might not be fixable at all.
Re:A Solution of the P versus NP Problem? by ouid on Tuesday August 15, 2017 @01:12PM (#15020150)
I think you missed the joke
Re:A Solution of the P versus NP Problem? by wolfgke on Monday August 14, 2017 @03:33PM (#15011984)
After overlooking the paper and applying Scott Aaronson's criterion I bet against you and bet:

- The proof will turn out to have a flaw

- The flaw will not be that hard to find (though probably not completely trivial; but rather of the kind: it takes much time to go to the details of the proof arguments)

- The flaw will not be interesting in itself and will not advance the field

Re:A Solution of the P versus NP Problem? by kittysasa on Monday August 14, 2017 @03:54PM (#15012216)
Seconded. The flaws in these papers are not hard to find. They usually amount to misunderstanding of definitions or the results they cite.
Re:A Solution of the P versus NP Problem? by westoncb on Monday August 14, 2017 @04:58PM (#15012817)
Unlikely considering the author of the paper. I'm basing that on other comments on the thread which this section seems to be missing, e.g.:

> ...this guy is an established senior researcher at the University of Bonn

Re:A Solution of the P versus NP Problem? by hnaccy on Monday August 14, 2017 @08:06PM (#15014202)
Even experienced people can make "silly" mistakes. https://arxiv.org/abs/1612.04208v1
Re:A Solution of the P versus NP Problem? by westoncb on Monday August 14, 2017 @09:03PM (#15014486)
They can—but that doesn't mean we should assume it's a silly mistake (as opposed to a deep one) without more information than that he's an accomplished researcher.
Re:A Solution of the P versus NP Problem? by KGIII on Monday August 14, 2017 @10:12PM (#15014787)
To add to this, I have a Ph.D. in applied mathematics. I am also an accomplished researcher, albeit retired.

I make more mistakes by 09:00 than most people will make all day. Hell, my girlfriend would suggest that we can move that time forward a couple of hours.