News for hackers. Stuff that matters.
Re: Wikipedia-size maths proof too big for humans to check by ColinWright on Wednesday February 19, 2014 @03:07PM (#7265867)
Because the output of the program is effectively a long list of cases of things that have been considered[0], and why they do or don't "work" in some sense. The output is independent of the program and, in principle, can be checked. In some ways it's like printing the search tree of chess to show that white has a forced win. It doesn't matter if the program is "correct" - you can check the output separately.

[0] EDIT: actually it's the certificate from a SAT solver

Re: Wikipedia-size maths proof too big for humans to check by samatman on Wednesday February 19, 2014 @03:34PM (#7266037)
I believe "Someone" is wondering whether it's possible, and if so helpful, to work out the common factors in those search trees and give them names, much as a certain chess search tree could efficiently be called "Stonewall White" if it represented all boards reachable from that class of opening.
Re: Wikipedia-size maths proof too big for humans to check by baddox on Wednesday February 19, 2014 @04:01PM (#7266196)
I get that, but all these articles are worried about the fact that no human could possibly read and verify the output of the program. So why even bother? Why not just verify the software and hardware that generates the output?
Re: Wikipedia-size maths proof too big for humans to check by ColinWright on Wednesday February 19, 2014 @04:08PM (#7266238)
It's a certificate output by a SAT solver. More, you can't guarantee that there wasn't a bit flip caused by a cosmic ray. Verifying the hardware and software isn't enough.

And yes, the whole question is to ask to what extent we can trust this. Personally, it's just as likely that a human proof would have a subtle and hard-to-find error, missed by all the reviewers.

All the popular articles are claiming this humungous output is a proof. It's not a proof, it's a certificate from a SAT solver. There's a difference, and most comments people are making based on the popular accounts are misguided.

Re: Wikipedia-size maths proof too big for humans to check by scott_s on Wednesday February 19, 2014 @04:22PM (#7266328)
If the certificate from the SAT solver does not count as a proof, you can't blame the popular accounts. That's the language the paper authors use:

The negative witness, that is, the DRUP unsatisfiability certificate, is probably one of longest proofs of a non-trivial mathematical result ever produced. Its gigantic size is comparable, for example, with the size of the whole Wikipedia, so one may have doubts about to which degree this can be accepted as a proof of a mathematical statement.

From http://arxiv.org/pdf/1402.2184v2.pdf

Re: Wikipedia-size maths proof too big for humans to check by ColinWright on Wednesday February 19, 2014 @04:42PM (#7266439)
I think the problem is that the general public think of "proof" as the kind of thing that mathematicians sit and work out with a pencil on paper. To use the word "proof" to refer to a certificate is technically correct and appropriate in context, but deeply misleading when used outside of that context. It certainly gives the wrong impression.

I also suspect we're mostly in complete agreement.

Re: Wikipedia-size maths proof too big for humans to check by Igglyboo on Wednesday February 19, 2014 @04:35PM (#7266404)
>More, you can't guarantee that there wasn't a bit flip caused by a cosmic ray.

You could just run the program and verify that the certificates match a few times, I guess you can't be 100% certain but the probability of a bit flip happening multiple times is extremely small.

Re: Wikipedia-size maths proof too big for humans to check by baddox on Wednesday February 19, 2014 @04:11PM (#7266251)
> More, you can't guarantee that there wasn't a bit flip caused by a cosmic ray.

Hmm. Are bit flips from cosmic rays more likely than a human making a mistake verifying a proof, or even a large number of humans making the same mistake?

Re: Wikipedia-size maths proof too big for humans to check by ColinWright on Wednesday February 19, 2014 @04:16PM (#7266287)
If one human makes the mistake, it's probably because it's a mistake that humans trained in this field are likely to make. Mistakes are not independent in this sense. Also, the number of humans capable of an in-depth analysis of the result is small, and they've mostly all got the same training, so if there's a subtle mistake, it's one to which they are all susceptible.
Re: Wikipedia-size maths proof too big for humans to check by igravious on Wednesday February 19, 2014 @06:00PM (#7267184)
Why can't it check for bit-flipping along the way and such like using techniques similar to error correction codes. And do every calc at least three times or something. Come on people, you're letting the side down!
Re: Wikipedia-size maths proof too big for humans to check by judk on Wednesday February 19, 2014 @04:32PM (#7266382)
What's the difference between a certificate and a proof?
Re: Wikipedia-size maths proof too big for humans to check by dragontamer on Wednesday February 19, 2014 @04:53PM (#7266516)
It takes a human to look at the certificate, to understand WTF was just solved by this program, and then demonstrate that the certificate actually lines up with the math problem.
Re: Wikipedia-size maths proof too big for humans to check by dllthomas on Wednesday February 19, 2014 @04:07PM (#7266227)
A CS prof I had held the position (in grading his tests - perhaps not generally) that "a proof is anything that convinces me you could write a proof". The program, along with an output saying "true", would seem to suffice under that metric.