4 ms·
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 no
by baddox 13y ago
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?
- dllthomas 13y agoA 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.
- ColinWright 13y agoIt'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.
- baddox 13y ago> 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?
- ColinWright 13y agoIf 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.
- scott_s 13y agoIf 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 http://arxiv.org/pdf/1402.2184v2.pdf
- ColinWright 13y agoI 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.
- judk 13y agoWhat's the difference between a certificate and a proof?
- dragontamer 13y agoIt 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.
- Igglyboo 13y ago>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.
- igravious 13y agoWhy 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!