We consider the basic problem of searching for an unknown m-bit number by asking the minimum possible number of yes-no questions, 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 answer to the ith question, the problem was posed by Ulam and Re' nyi and is strictly related to Berlekamp's theory of error correcting communication 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 q{sub}e(m) be the smallest integer q satisfying Berlekamp's bound (∑{sub}(i=0)){sup}e (q{down}i) ≤ 2{sup}(q-m). Then at least q{sub}e(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 q{sub}e(m) questions always exist up to finitely many exceptional m's. At the opposite non-adaptive case, searching strategies with exactly q{sub}e(m) questions-or equivalently, e-error correcting codes with 2{sup}m codewords of length q{sub}e(m)-are rather the exception, already for e=2, and are generally not known to exist for e >2. In this paper, for each e> 1 and all sufficiently large m, we exhibit searching strategies that use a first batch of m non-adaptive questions and then, only depending on the answers to these m questions, a second batch of q{sub}e(m) - m non-adaptive questions. These strategies are automatically optimal. Since even in the fully adaptive case, q{sub}e(m)- 1 questions do not suffice to find the unknown number, and q{sub}e(m) questions generally do not suffice in the non-adaptive case, the results of our paper provide e fault tolerant searching strategies with minimum adaptiveness and minimum number of tests.
展开▼
