We consider the problem of determining the minimum number of queries to find an unknown number in a finite set when up to a finite number e of the answers may be erroneous. In the vast literature regarding this problem, the classical case of binary search is mostly con- sidered, that is, when only yes-no questions are allowed. In this paper we consider the variant of the problem in which questions with q many possible answers are allowed. We prove that at most one question more than the information theoretic lower bound is sufficient to successfully find the unknown number. Moreover we prove that there are infinitely many cases when the information theoretic lower bound is exactly attained and the so called perfect strategies exist. Our strategies have the important feature that they use a minimum amount of adaptiveness, a relevant property in many practical situation.
QUASI -PERFECT MINIMALLY ADAPTIVE Q-ARY SEARCH WITH UNRELIABLE TESTS
CICALESE, Ferdinando;
2003
Abstract
We consider the problem of determining the minimum number of queries to find an unknown number in a finite set when up to a finite number e of the answers may be erroneous. In the vast literature regarding this problem, the classical case of binary search is mostly con- sidered, that is, when only yes-no questions are allowed. In this paper we consider the variant of the problem in which questions with q many possible answers are allowed. We prove that at most one question more than the information theoretic lower bound is sufficient to successfully find the unknown number. Moreover we prove that there are infinitely many cases when the information theoretic lower bound is exactly attained and the so called perfect strategies exist. Our strategies have the important feature that they use a minimum amount of adaptiveness, a relevant property in many practical situation.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
