Combinatorial Search Problems
Search problems are among the basic problems in Computer Science. The classical searching problem is: given a list of numbers, with some possible additional constraints, determine the position/existence of a given number in the list. In particular, when the list is sorted, binary search finds the required element with an optimal number of comparisons (queries). Several variants of this basic problems exists. We are currently studing Group testing problems and Searching with Lies.
A well-studied combinatorial search problem is the group testing problem: given a population of n items consisting of d defective and (n-d) good items, the problem consists of finding all of the defective items by using a series of group tests. A group test is a simultaneous test on the defectiveness of the elements of an arbitrary subset X of P. The problem apparently goes back to questions arising in connection with medical examinations during the Second World War. Several versions of this problem have been considered in the literature, recent results shows the relevance of group testing problem in computational biology
