3 ms·
The problem is we can't believe things like "we sampled the first 10^6 examples we came up with and it held so we can trust it to be valid". These are still jus
by zamadatix 3y ago
The problem is we can't believe things like "we sampled the first 10^6 examples we came up with and it held so we can trust it to be valid". These are still just conjectures and sometimes turn out to be false at extreme bounds or corner cases. This doesn't mean conjectures (or even known sometimes-false approximations) are useless, it's just a different discussion vs what is trying to be done with these tools.
One case you can get away with this is exhaustively checking the ENTIRE search space. E.g. I can prove an 8 bit addition circuit by testing every combination of 8 bit numbers and verifying the outputs match the goal values. I can't prove the same circuit by running 200 random additions and saying "none of these had errors, must be good", despite being extremely confident in it. The problem with a lot of actual math things is the search space is infinite (see the number of possible real coefficients in a quadratic function) unless you start doing smart things to limit the bounds of what you need to check, which comes back to logical theorem proving tactics. Sometimes a combination of these methods is used, e.g. the initial validations of the 4 color theorem, where you limit the search space to something reasonable but not prove it straight out then simply check the remaining cases.
For a famous example, take Skewe's number. It's an upper bound for when the number of primes below x finally exceeds the logarithmic integral approximation of the same value but even the lower bound is ridiculously high. We have a logical proof the functions swap who is greater an infinite number of times but it'd be quite easy to run some test like this with floats and still conclude we've proven li(x) < pi(x). Heck, it's even possible the gaps in floats at that scale are large enough to just skip a crossover entirely.
- gosub100 3y agothank you for the detailed answer :)