REAL

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.

[img]
Preview
Text
paper_139.pdf

Download (221Kb) | 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.

Item Type: Book Section
Uncontrolled Keywords: Problem solving; INFORMATION THEORY; Partial results; Mathematical problems; Know-that; Combinatorial problem; search with lies; Combinatorial search
Subjects: Q Science / természettudomány > QA Mathematics / matematika
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 29 Jan 2015 19:35
Last Modified: 29 Jan 2015 19:35
URI: http://real.mtak.hu/id/eprint/21051

Actions (login required)

View Item View Item