Don, if n is big enough then sure, I’m more than willing to play your game (assuming I get something out of it if I win).
My randomised algorithm will get the right answer within 4 tries in expectation. If I’m allowed to sample a thousand bits then the probability that it won’t have found the answer by then is .75^1000 which I think is something like 10^-120. And this applies even if you’re allowed to choose the string after looking at my algorithm.
If you play the game this way with your deterministic algorithm you will always need to sample n/4 + 1 bits—I can put the ones where you’ll never find them. If you don’t like this game, fine don’t do computational complexity, but there’s nothing wrong with Scott’s argument.
Yes, we assume that you can’t predict what random bits I will generate before I generate them, but that’s pretty much what random means, so I don’t see why it’s such a big deal.
Don, if n is big enough then sure, I’m more than willing to play your game (assuming I get something out of it if I win).
My randomised algorithm will get the right answer within 4 tries in expectation. If I’m allowed to sample a thousand bits then the probability that it won’t have found the answer by then is .75^1000 which I think is something like 10^-120. And this applies even if you’re allowed to choose the string after looking at my algorithm.
If you play the game this way with your deterministic algorithm you will always need to sample n/4 + 1 bits—I can put the ones where you’ll never find them. If you don’t like this game, fine don’t do computational complexity, but there’s nothing wrong with Scott’s argument.
Yes, we assume that you can’t predict what random bits I will generate before I generate them, but that’s pretty much what random means, so I don’t see why it’s such a big deal.