论文标题
殴打税务员的困难
The difficulty of beating the Taxman
论文作者
论文摘要
事实证明，税务员游戏很难最佳解决，因此已经努力寻找在实践中做得很好的启发式策略。我们通过与特定类型的图形匹配问题的等效性介绍了游戏变体的NP硬度。此外，此等效性用于为所有$ n $提供成功的策略，以及在最佳实现分数上有效地计算的下限和上限。
The Taxman game has proven to be hard to solve optimally, so efforts have been made to find heuristic strategies that do well in practice. We present results on the NP-hardness of a variant of the game via an equivalence to a particular kind of graph matching problem. Furthermore this equivalence is used to derive a winning strategy for all $n$ along with efficiently computable lower and upper bounds on the optimal achievable score.
