ABSTRACT
How many yes-no questions do we need to ask to find an unknown element of a set X of size n? This is the starting point of combinatorial search theory. We assume that the set of elements is [n], and the questions are of the form whether the unknown element belongs to a subset F of [n]. The answer is YES or NO. By halving the possibilities with each question, one may get an algorithm that finds the unknown element with [log n] questions, but the questions of this algorithm depend on the answers we obtained to previous questions. These type of algorithms are called adaptive. One can achieve the same goal with the same number of questions without relying on previous answers (a non-adaptive algorithm), by asking the sets F i = { x ∈ [ n ] : https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429440809/2714d8f8-ef71-44f4-80bb-22c5d5471b0d/content/eq8240.tif"/> : the ith bit of x in its binary form is 1}. One cannot do better neither adaptively, nor non-adaptively, as if k questions are asked, then the number of possible sequences of answers is 2 k . To be able to distinguish between the cases when x or y is the unknown element, the corresponding sequences of answers should differ; therefore we must have 2 k ≥ n.
