@ John, @ Scott: You’re still doing something odd here. As has been mentioned earlier in the comments, you’ve imagined a mind-reading superintelligence … except that it doesn’t get to see the internal random string.
Look, this should be pretty simple. The phrase “worst case” has a pretty clear layman’s meaning, and there’s no reason we need to depart from it.
You’re going to get your string of N bits. You need to write an algorithm to find the 1s. If your algorithm ever gives the wrong answer, we’re going to shoot you in the head with a gun and you die. I can write a deterministic algorithm that will do this in at most n/4+1 steps. So we’ll run it on a computer that will execute at most n/4+1 queries of the input string, and otherwise just halt (with some fixed answer). We can run this trillions of times, and I’m never getting shot in the head.
Now, you have a proposal. You need one additional thing: a source of random bits, as an additional input to your new algorithm. Fine, granted. Now we’re going to point the gun at your head, and run your algorithm trillions of times (against random inputs). I was only able to write a deterministic algorithm; you have the ability to write a randomized algorithm. Apparently you think this gives you more power.
Now then, the important question: are you willing to run your new algorithm on a special computer that halts after fewer than n/4+1 queries of the input string? Do you have confidence that, in the worst case, your algorithm will never need more than, say, n/4 queries?
No? Then stop making false comparisons between the deterministic and the randomized versions.
@ John, @ Scott: You’re still doing something odd here. As has been mentioned earlier in the comments, you’ve imagined a mind-reading superintelligence … except that it doesn’t get to see the internal random string.
Look, this should be pretty simple. The phrase “worst case” has a pretty clear layman’s meaning, and there’s no reason we need to depart from it.
You’re going to get your string of N bits. You need to write an algorithm to find the 1s. If your algorithm ever gives the wrong answer, we’re going to shoot you in the head with a gun and you die. I can write a deterministic algorithm that will do this in at most n/4+1 steps. So we’ll run it on a computer that will execute at most n/4+1 queries of the input string, and otherwise just halt (with some fixed answer). We can run this trillions of times, and I’m never getting shot in the head.
Now, you have a proposal. You need one additional thing: a source of random bits, as an additional input to your new algorithm. Fine, granted. Now we’re going to point the gun at your head, and run your algorithm trillions of times (against random inputs). I was only able to write a deterministic algorithm; you have the ability to write a randomized algorithm. Apparently you think this gives you more power.
Now then, the important question: are you willing to run your new algorithm on a special computer that halts after fewer than n/4+1 queries of the input string? Do you have confidence that, in the worst case, your algorithm will never need more than, say, n/4 queries?
No? Then stop making false comparisons between the deterministic and the randomized versions.