Silas: “Solve” = for a worst-case string (in both the deterministic and randomized cases). In the randomized case, just keep picking random bits and querying them. After O(1) queries, with high probability you’ll have queried either a 1 in the left half or a 1 in the right half, at which point you’re done.
As far as I know this problem doesn’t have a name. But it’s how (for example) you construct an oracle separating P from ZPP.
Silas: “Solve” = for a worst-case string (in both the deterministic and randomized cases). In the randomized case, just keep picking random bits and querying them. After O(1) queries, with high probability you’ll have queried either a 1 in the left half or a 1 in the right half, at which point you’re done.
As far as I know this problem doesn’t have a name. But it’s how (for example) you construct an oracle separating P from ZPP.