Introduction to Search Theory and a result when the lie depends on the question

Gyula O.H. Katona

ABSTRACT: In the basic model of search an n-element set X is given which contains an unknown, but important element x. The goal is to find x. Questions of type "is x&isinA?" can be asked for certain subsets A&sub X. The number of questions should be minimized necessary to find x. Another model is the traditional "search with lies" when the answers for the questions "is x&isinA?" can be wrong with certain restrictions, but the chance of the false answer does not depend on x or A. The first part of the lecture will give a brief survey of this theory.

In the second half of the lecture the speaker will introduce a recent work with Krisztián Tichler in which the questions have a different nature. Namely one question is a partition Y,N,L of X. If x&isinY the answer will be "yes" and we can be sure that x is in Y. The same if x&isinN. However if x&isinL the the answer might be "yes" or "no", that is, no useful information is received. We found minimal algorithms finding an arbitrary x under such circumstances.