Combinatorial search theory
Dániel Gerbner, Balázs Patkós · 2018
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 i th 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 .