Search when the lie depends on the target

Katona, Gyula and Tichler, K. (2013) Search when the lie depends on the target. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 7777. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (7777). Springer Verlag, Berlin; Heidelberg, pp. 648-657.

Preview

Text paper_139.pdf Download (226kB) | Preview

Abstract

The following model is considered. There is exactly one unknown element in the n-element set. A question is a partition of S into three classes: (A,L,B). If x ∈ A then the answer is "yes" (or 1), if x ∈ B then the answer is "no" (or 0), finally if x ∈ L then the answer can be either "yes" or "no". In other words, if the answer "yes" is obtained then we know that x ∈ A ∪ L while in the case of "no" answer the conclusion is x ∈ B ∪ L. The mathematical problem is to minimize the minimum number of questions under certain assumptions on the sizes of A,B and L. This problem has been solved under the condition |L| ≥ k by the author and Krisztián Tichler in previous papers for both the adaptive and non-adaptive cases. In this paper we suggest to solve the problem under the conditions |A| ≤ a, |B| ≤ b. We exhibit some partial results for both the adaptive and non-adaptive cases. We also show that the problem is closely related to some known combinatorial problems. Let us mention that the case b = n - a has been more or less solved in earlier papers. © Springer-Verlag Berlin Heidelberg 2013.

Actions (login required)

Edit Item