Perfect Two-Fault Tolerant Search with Minimum Adaptiveness

AbstractOur aim is to minimize the number of answer/question alternations in a perfect two-fault-tolerant search. Ulam and Rényi posed the problem of searching for an unknown m-bit number by asking the minimum number of yes–no questions, when up to ℓ of the answers may be erroneous/mendacious. Berlekamp considered the same problem in the context of error-correcting communication with feedback. Among others, he proved that at least qℓ(m) questions are necessary, where qℓ(m) is the smallest integer q satisfying 2q−m≥∑ℓj=0(qj). When all questions are asked in advance, and adaptiveness has no role, finding a perfect strategy (i.e., a strategy with qℓ(m) questions) amounts to finding an ℓ-error-correcting code with 2m codewords of length qℓ(m). From coding theory it is known that such perfect non-adaptive searching strategies are rather the exception, for ℓ≥2. At the other extreme, in a fully adaptive search, where the (t+1)th question is asked knowing the answer to the tth question, perfect strategies are known to exist for all sufficiently large m.What happens if we impose restrictions on the amount of adaptiveness avaliable to the questioner? Focusing attention on the case ℓ=2, we shall prove that, for each m≠2, perfect searching strategies still exist even if the questioner is allowed to adapt his strategy only once. All our results are constructive and explicitly yield perfect two-error-correcting codes with the least possible feedback. We finally generalize our results to k-ary search