2013 | OriginalPaper | Chapter
Search When the Lie Depends on the Target
Authors : Gyula O. H. Katona, Krisztián Tichler
Published in: Information Theory, Combinatorics, and Search Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.