LEAST ADAPTIVE OPTIMAL SEARCH WITH UNRELIABLE TESTS

We consider the basic problem of searching for an unknown m-bit number by asking the minimum possible number of yes-no ques-tions, when up to a finite number e of the answers may be erroneous. In case the (i + 1)th question is adaptively asked after receiving the an-swer to the ith question, the problem was posed by Ulam and Rényi and is strictly related to Berlekamp's theory of error correcting communica-tion with noiseless feedback. Conversely, in the fully non-adaptive model when all questions are asked before knowing any answer, the problem amounts to finding a shortest e-error correcting code. Let qe(m) be the smallest integer q satisfying Berlekamp's bound ∑ei=0(qi)≤2q-m: Then at least qe(m) questions are necessary, in the adaptive, as well as in the non-adaptive model. In the fully adaptive case, optimal searching strategies using exactly qe(m) questions always exist up to finitely many exceptional m's. At the opposite non-adaptive case, searching strategies with exactly qe(m) questions—or equivalently, perfect e-error correct-ing codes with 2m codewords of length qe(m)—are rather the exception, already for e = 2, and do not exist for e > 2. In this paper we show that for any e > 1 and sufficiently large m, optimal—indeed, perfect—strategies do exist using a first batch of m non-adaptive questions and then, only depending on the answers to these m questions, a second batch of qe(m)−m non-adaptive questions. Since even in the fully adap-tive case, qe(m)−1 questions do not sufice to find the unknown number, and qe(m) questions generally do not sufice in the non-adaptive case, the results of our paper provide e-fault tolerant searching strategies with minimum adaptiveness and minimum number of tests.