SEARCHING WITH LIES

Let f(t)(n) be the number of questions necessary to find an unknown el ement out of a set of n elements with a q-ary search process when up t o t answers may be wrong (are lies). For q = 2, this problem was treat ed by several authors. We give the complete solution for t = 1 and der ive bounds for general t. Further, it is shown that the corresponding function g(1)(n) for the non-adaptive case (which requires constructio n of 1-error correcting codes) differs from f(1)(n) by at most 1, when q is a prime power. (C) 1996 Academic Press, Inc.