论文标题
具有线性数量查询的策划者
Mastermind with a Linear Number of Queries
论文作者
论文摘要
自1960年代以来，已经研究了游戏必须提供的组合和信息理论兴趣。从Erdős和Rényi开始，确定两种颜色所需的最佳查询数量，从而发现了许多结果。对于$ k $颜色和$ n $位置，当$ k \ le n^{1-ε} $时，Chvátal发现了渐近最佳界限。遵循$ k \ geq n $颜色的一系列逐步改进，中心的开放问题是解决$ω（n）$和$ \ natercal {o}（n \ log \ log \ log n）$之间的差距，$ k = n $。 在本文中，我们通过提出第一个用于求解$ k = n $策划者的算法来解决此差距，并具有线性的查询。结果，我们能够确定任何参数$ k $和$ n $的策划者的查询复杂性。
Since the 1960s Mastermind has been studied for the combinatorial and information theoretical interest the game has to offer. Many results have been discovered starting with Erdős and Rényi determining the optimal number of queries needed for two colors. For $k$ colors and $n$ positions, Chvátal found asymptotically optimal bounds when $k \le n^{1-ε}$. Following a sequence of gradual improvements for $k \geq n$ colors, the central open question is to resolve the gap between $Ω(n)$ and $\mathcal{O}(n\log \log n)$ for $k=n$. In this paper, we resolve this gap by presenting the first algorithm for solving $k=n$ Mastermind with a linear number of queries. As a consequence, we are able to determine the query complexity of Mastermind for any parameters $k$ and $n$.
