Perfect Two-Fault Tolerant Search with Minimum Adaptiveness
Source: Advances in Applied Mathematics, Volume 25, Number 1, July 2000 , pp. 65-101(37)
Publisher: Academic Press
Abstract:Our 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.
Document Type: Research Article
Affiliations: 1: Department of Computer Science and Applications, University of Salerno, Via S. Allende, Baronissi (Salerno), 84081, Italy 2: Department of Computer Science, University of Milan, Via Comelico 39-41, Milan, 20135, Italy
Publication date: July 1, 2000