Paper Info
Title
Search when the lie depends on the target
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.
Year
Venue
Keywords
2013
Information Theory, Combinatorics, and Search Theory
n-element set,certain assumption,known combinatorial problem,n tichler,partial result,earlier paper,minimum number,mathematical problem,following model,non-adaptive case
Field
DocType
Citations 
Discrete mathematics,Artificial intelligence,Combinatorial search,Partition (number theory),Mathematics,Mathematical problem
Conference
0
PageRank 
References 
Authors
0.34
4
2
Name
Order
Citations
PageRank
Gyula O. H. Katona126466.44
Krisztián Tichler2182.45