科研之友
微信
新浪微博
Facebook
分享链接
摘要
To detect an unknown element x* from a finite set S = {1, 2, ... , n} by asking group-testing queries is a classical combinatorial optimization problem. We consider a variation of the problem, what we call the liar search game with small sets vertical bar n, e, <= k vertical bar and formulate it as follows: two players, say Paul and Carole, fix integers k >= 1, m > 0 and e >= 0 beforehand. Paul asks size restricted queries to find x*: "Is x* in A?", where A subset of S and vertical bar A vertical bar <= k. Carole answers them with "Yes" or "No" to tell whether x* belongs to A or not. Carole is permitted to lie at most e times. Paul wins if he finds x* within m rounds; otherwise Carole wins. Our goal is to determine the minimum value of m to assure Paul to win. Let f (n, e, <= k) = min{m vertical bar Paul wins the game [n, e, <= k] for the given integer m}. In this paper, we consider the sequential algorithms of the above game and obtain a tight bound L-upper(n, 1, <= k) such that f (n, 1, <= k) <= L-upper(n, 1, <= k) <= f (n, 1, <= k) + 1, and the exact value off (n, 1, <= k) for (1) n <= 2k + 1 and (2) n >= k(2) except for the case n = 15 and k = 3. Moreover, in the end of this paper, we conjecture the exact value off (n, 1, <= k) for general case and verify its correctness for k = infinity.
