For this purpose, consider an arbitrary algorithm A that merges sequences u_{1}, u_{2}, ...., u_{n} and v_{1}, v_{2}, ...., v_{n} such that
repeat u_{i} and v_{j} = the next pair of keys to be compared; if i=j then answer "u_{i} precedes v_{j}" else if i<j then answer "u_{i} precedes v_{j}" else answer "v_{j} precedes u_{i}" end end endAnother way of describing this algorithm is saying
(u_{1} and v_{1}), (v_{1} and u_{2}), (u_{2} and v_{2}), ... , (v_{n-1} and u_{n}), (u_{n} and v_{n})of keys that are adjacent in the input template remains uncompared, and so the answers provided by the oracle match not only this template, but also the template where the order of these two keys is switched.
For example, let us take n=5. If u_{2} and v_{2} remain uncompared, then the answers provided by the oracle match both templates
u_{1} < v_{1} < u_{2} < v_{2} < u_{3} < v_{3} < u_{4} < v_{4} < u_{5} < v_{5}and
u_{1} < v_{1} < v_{2} < u_{2} < u_{3} < v_{3} < u_{4} < v_{4} < u_{5} < v_{5}.If v_{3} and u_{4} remain uncompared, then the answers provided by the oracle match both templates
u_{1} < v_{1} < u_{2} < v_{2} < u_{3} < v_{3} < u_{4} < v_{4} < u_{5} < v_{5}and
u_{1} < v_{1} < u_{2} < v_{2} < u_{3} < u_{4} < v_{3} < v_{4} < u_{5} < v_{5}.And so on.
For this purpose, consider an arbitrary algorithm A that finds the largest of keys u_{1}, u_{2}, ...., u_{n} and accesses the input only through the comparison oracle. Let us simulate the oracle by the following algorithm:
for i = 1 to n do candidate(u_{i})=YES end repeat u_{i} and u_{j} = the next pair of keys to be compared; if i<j then answer "u_{i} precedes u_{j}" candidate(u_{i})=NO; else answer "u_{j} precedes u_{i}" candidate(u_{j})=NO; end endAnother way of describing this oracle is saying
u_{1} < u_{2} < ... < u_{k-1} < u_{k+1} < ... < u_{n} < u_{k}.
u_{1} < v_{1} < u_{2} < v_{2} < ... < u_{n} < v_{n} in Example 1and
u_{1} < u_{2} < ... < u_{n} in Example 2,and answer all questions as if the unknown input matched this template. Such oracle simulations might be called non-adaptive. More sophisticated oracle simulations construct the template incrementally in a way that depends on A's questions. One example of such an adaptive oracle simulation is coming up next.
For this purpose, consider an arbitrary algorithm A that finds the median of a set S of 2k+1 keys and accesses the input only through the comparison oracle. Let us simulate the oracle by the following algorithm:
/* Initialization */ for all elements u of S do rank(u) = "unassigned"; candidate(u) = YES; end /* Adaptive stage */ num_small = 0, num_large = 0; while num_small < k and num_large < k do u,v = the next pair of keys to be compared; if rank(u) = "unassigned" then if rank(v) = "unassigned" then num_small = num_small+1, rank(u) = num_small; num_large = num_large+1, rank(v) = k+1+num_large; else if rank(v) < k+1 then num_large = num_large+1, rank(u) = k+1+num_large; else num_small = num_small+1, rank(u) = num_small; end end else if rank(v) = "unassigned" then if rank(u) < k+1 then num_large = num_large+1, rank(v) = k+1+num_large; else num_small = num_small+1, rank(v) = num_small; end end end if rank(u) < rank(v) then answer "u precedes v" if k+1 < rank(u) then candidate(v) = NO end if rank(v) < k+1 then candidate(u) = NO end else answer "v precedes u" if k+1 < rank(v) then candidate(u) = NO end if rank(u) < k+1 then candidate(v) = NO end end end /* Completing the template */ w = an element of S such that rank(w) = "unassigned"; rank(w) = k+1; if num_small = k then for all elements u of S do if rank(u) = "unassigned" then num_large = num_large+1, rank(u) = k+1+num_large; end end else for all elements u of S do if rank(u) = "unassigned" then num_small = num_small+1, rank(u) = num_small; end end end /* Non-adaptive stage */ repeat u,v = the next pair of keys to be compared; if rank(u) < rank(v) then answer "u precedes v"; if rank(u) is at least k+1 then candidate(v) = NO end if rank(v) is at most k+1 then candidate(u) = NO end else answer "v precedes u"; if rank(v) is at least k+1 then candidate(u) = NO end if rank(u) is at most k+1 then candidate(v) = NO end end endLet us say that a call of oracle is useful if it brings about setting
candidate(w)=NO
for some w
. In the
adaptive stage, at least k calls of the oracle are countered by
setting the value of rank(u) or rank(v) or both in such a way that
the smaller of rank(u), rank(v) is smaller than k+1 andnone of these calls are useful. It follows that, as long as A calls the oracle fewer than 3k times, at most 2k-1 of these calls are useful, and so in the end at least two distinct elements
the larger of rank(u), rank(v) is larger than k+1;
w
of S have candidate(w)=YES
. In
particular, there is an element x
of S such that
rank(x)
is not k+1
and such that
candidate(x)=YES
. If rank(x) < k+1, then set
newrank(x) = k+1, newrank(y) = rank(y)-1 whenever rank(x) < rank(y) < k+2, newrank(y) = rank(y) for all other choices of y;if rank(x) > k+1, then set
newrank(x) = k+1, newrank(y) = rank(y)+1 whenever k < rank(y) < rank(x), newrank(y) = rank(y) for all other choices of y;The answers that oracle has provided are consistent with the linear order defined by rank(.) as well as with the linear order defined by newrank(.). However, the median with respect to rank(.) differs from x, which is the median with respect to newrank(.).
We propose to show that
For this purpose, consider an arbitrary algorithm A that finds the counterfeit in a set P of n coins and accesses the input only through the use of pharmacy scales. Let us simulate the outcomes of the weighings by the following algorithm:
repeat L,R = the two sets of coins to be placed on the two trays; /* we have |L|=|R| */ if |L| > |P|/3 then answer "L is lighter than R"; P = L; else answer "L and R are of equal weight"; remove both L and R from P; end /* the counterfeit is in P */ endAfter t iterations, the size of P is at least n / 3^{t} . In particular, if t < lg n / lg 3, then the size of P is greater than 1, and so the answers that the oracle has provided are consistent with at least two distinct choices of the counterfeit.
For this purpose, consider an arbitrary algorithm A that sorts a set S of n keys and accesses the input only through the comparison oracle. Let us simulate the oracle by the following algorithm:
P = the set of all linear orders on S; repeat u,v = the next pair of keys to be compared; P(u) = the set of all linear orders in P where u precedes v; P(v) = the set of all linear orders in P where v precedes u; if |P(u|) > |P(v)| then answer "u precedes v"; P = P(u); else answer "v precedes u"; P = P(v); end endAfter t iterations, the size of P is at least n! / 2^{t} . In particular, if t < lg(n!), then the size of P is greater than 1, and so the answers that the oracle has provided are consistent with at least two distinct linear orders on S.
If A is an algorithm that attempts to determine g(x) of an unknown input x by calling the oracle as few times as possible, then an adversary strategy against A simulates the oracle in a way that attempts to keep g(x) unknown as long as possible. The non-adaptive adversary strategies are particularly simple: they have the form
choose an element y of P; repeat f = the next function in Q for which the oracle is asked to return f(x); answer "f(y)"; end
The adaptive adversary strategies used in Examples 4 and 5 generalize as follows:
repeat f = the next function in Q for which the oracle is asked to return f(x); w = an element of f(P) that maximizes |{g(x) : x is in P and f(x)=w}|; answer "w"; P = {x : x is in P and f(x)=w}; endTo analyze this algorithm, let us write