It's worse: Pr[correct output | hard input] = 0, even though they estimate that Pr[correct output | random input] ~ 1. This means that you can't, for example, amplify your success probability by repeating the algorithm a bunch of times and taking the majority vote.
The challenge is to get the right answer. It's much less interesting if you relax the challenge to no longer require the right answer. Here's a really fast approximate answer: 50000000*(2^31-1)/2
Comments
That's terrifying
It's worse: Pr[correct output | hard input] = 0, even though they estimate that Pr[correct output | random input] ~ 1. This means that you can't, for example, amplify your success probability by repeating the algorithm a bunch of times and taking the majority vote.
Why? So long as you know the probabilities and they are tolerable, why?
The challenge is to get the right answer. It's much less interesting if you relax the challenge to no longer require the right answer. Here's a really fast approximate answer: 50000000*(2^31-1)/2
Map vs. territory. The challenge, as defined by the system the competition runs on, is to get 3 correct responses in a row. That's it.
The fact that it's wrong sometimes is a lot less interesting than the probability distribution of wrongness, conditional on magnitude.
Solid point and good example