An adversary selects an integer k from the set of non-negative integers.
Does any algorithm exist that, using only tests for equality or inequality (<, =, >), is guaranteed to find k in finite time?
$\begingroup$
$\endgroup$
8
-
$\begingroup$ What's wrong with trying $1,2,\ldots,k$ and testing equality each time? $\endgroup$– Alex BeckerApr 2, 2012 at 5:34
-
$\begingroup$ Given that the set of non-negative integers is infinite, my understanding is that there is no guarantee to complete in finite time. $\endgroup$– Eric J.Apr 2, 2012 at 5:36
-
$\begingroup$ It would find $\rm k$ after precisely $\rm k$ equality tests no? $\endgroup$– anonApr 2, 2012 at 5:37
-
$\begingroup$ It will, because the number your adversary has selected is finite. But true there is no upper bound on how long it will take. $\endgroup$– Alex BeckerApr 2, 2012 at 5:37
-
1$\begingroup$ Imagine that your adversary just pretends to select an integer. Whatever sequence of tests you name, the adversary can always give you an answer satisfied by infinitely many non-negative integers. If you can only run a bounded number of tests, then after you give up the adversary can reveal a number as if it had been selected at the start. $\endgroup$– Gerry MyersonApr 2, 2012 at 5:46
|
Show 3 more comments
3 Answers
$\begingroup$
$\endgroup$
5
At step $n$ test the non-negative integer $n-1$ for equality; you are guaranteed to find $k$ on step $k+1$, so the algorithm is guaranteed to terminate after a finite number of steps, though the possible stopping times are unbounded. What is not possible is to put a fixed limit on the search time beforehand: no matter what algorithm you use, for any $n$ there will be values of $k$ that cannot be found within $n$ steps.
answered Apr 2, 2012 at 5:44
-
$\begingroup$ I'm having trouble with the following: It seems to me that for any
n'th iteration of any algorithm that tests integert, if I plotton the number line, there are a bound number of integers less thantand an unbound number of integers to the right oft. Given that the number of integers to the right oftis always unbound for any iteration, it seems the probability of findingkon then'th iteration is vanishingly small. What is wrong with that logic? Is that Zeno in a differeng guise? $\endgroup$– Eric J.Apr 2, 2012 at 5:57 -
$\begingroup$ @EricJ. Probability isn't what you should consider here, because we are considering a fixed number picked by the opponent. All that matters is that that number is some finite number, so will eventually be found by testing sequential numbers. $\endgroup$ Apr 2, 2012 at 5:59
-
$\begingroup$ @Eric: Think about it: if you pick $k$, and then I guess $0,1,2,\dots$, the probability that I will eventually guess your $k$ is $1$. It just may take a long time. $\endgroup$ Apr 2, 2012 at 6:01
-
$\begingroup$ @Brian: What I still can't get my head around is, if k is drawn from an infinite set, why "a long time" is finite. $\endgroup$– Eric J.Apr 2, 2012 at 23:53
-
1$\begingroup$ @Eric: Suppose that you pick $k=10^{100}$; my algorithm will find it on step $10^{100}+1$. That’s a very long time, but it’s still finite. For any specific $k$ the amount of time needed is finite, though if $k$ is large, the amount of time needed will also be large. You keep ignoring the fact that in any given play of the game, $k$ is a fixed non-negative integer. It’s not floating around in the non-negative integers. It’s a single definite number, and if I count long enough, I will hit it. $\endgroup$ Apr 3, 2012 at 0:00
$\begingroup$
$\endgroup$
4
As pointed out in the comments and in Brian's answer, checking $0,\ldots,k$ for equality will give you the answer in $k+1$ steps. You can improve on this by testing $2,2^2,\ldots,2^{\lceil\log k\rceil}$ for the inequality $\leq$ and then testing $2^{\lceil \log k\rceil-1}+2,\ldots,2^{\lceil \log k\rceil-1}+2^{\lceil \log k\rceil-1}$ with $\leq$, on and on as much as necessary. However, as Brian points out no algorithm can guarantee that for any $k$ it will give you the answer in a certain number of steps. To make this explicit, suppose you had an algorithm guaranteed to work in $n$ steps. For any test there are at most two results, so the algorithm has at most $2^n$ possible outputs. Your opponent then needs only choose a number greater than any of these $2^n$ outputs to defeat it.
answered Apr 2, 2012 at 5:57
-
$\begingroup$ I guess the point I'm failing to understand is, why is n finite if, for ANY iteration n I can select some value k such that the algorithm has not yet determined k? It seems, were I a diabolical adversary, I would continue to play the game forever (for an infinite amount of time). $\endgroup$– Eric J.Apr 2, 2012 at 15:55
-
$\begingroup$ @EricJ. Just to clarify, your opponent makes a choice for $k$, after which his choice is completely fixed and cannot change, and then you run your algorithm. Correct? $\endgroup$ Apr 2, 2012 at 16:43
-
$\begingroup$ Yes. However, it seems to me that any number a diabolical adversary could selecting by "moving the target" could just as well have been the original choice. I guess bottom line, I don't grasp given an infinite set of numbers the original number was drawn from, why it is guaranteed that non-infinite number of iterations of an algorithm can discover it. The diabolical adversary is a mechanism I'm trying to use to understand that problem. $\endgroup$– Eric J.Apr 2, 2012 at 18:01
-
$\begingroup$ The point is that the adversary can't move the target after he made his choice. Here's the situation: he chose $k$. You test $1$, the answer is no. You test $2$, so on and so forth. Eventually you test $k$ and the answer will be yes. He can't move the target once he made his choice. It is fixed for however long it takes you to find it. $\endgroup$ Apr 3, 2012 at 1:04
$\begingroup$
$\endgroup$
2
Let's think about this from the perspective of the adversary. If we know that the player is going to try every non-negative integer in order, what number can we pick so that it takes her an infinite amount of time to guess it?
Clearly we can't pick $0$, she'll guess that right away! Picking 1 buys us a little time, but not much. 2, 3 and 4 will also be guessed quickly. Each higher number we consider takes a bit longer, but still isn't infinite. By induction, we're forced to concede that there is no number for us to pick that will take an infinite amount of time to guess. The reason for this is that even though there are an infinite number of integers, all of them are finite.
-
$\begingroup$ Just saw the date on the question. Sorry about the late answer. $\endgroup$– finteliaJul 15, 2014 at 20:25
-