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.

LEAST ADAPTIVE OPTIMAL SEARCH WITH UNRELIABLE TESTS / D. MUNDICI; F. CICALESE; U. VACCARO. - STAMPA. - (2000), pp. 549-562. [10.1007/3-540-44985-X]

LEAST ADAPTIVE OPTIMAL SEARCH WITH UNRELIABLE TESTS

MUNDICI, DANIELE;
2000

Abstract

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.
2000
7th Scandinavian Workshop on Algorithm Theory, SWAT 2000
549
562
D. MUNDICI; F. CICALESE; U. VACCARO
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/3619
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 6
social impact