论文标题
分类球和水：等效性和计算复杂性
Sorting Balls and Water: Equivalence and Computational Complexity
论文作者
论文摘要
多年来，已经研究了各种形式的分类问题。最近，普及了两种排序拼图应用程序。在这些难题中，我们给了一组装满彩色单元，球或水的垃圾箱，以及一些空的垃圾箱。当涉及的颜色以某种方式匹配或目标箱为空时，这些难题使我们能够将彩色单元从垃圾箱移动到另一个垃圾箱。这些难题的目的是按顺序对所有颜色单位进行排序。我们研究了这些难题的计算复杂性。我们首先表明，从解决性的角度来看，这两个难题本质上是相同的。也就是说，当且仅当它是由水动物分类时，一个实例可以被球体动物分类。我们还表明，每个固定的情况都具有多项式长度的解决方案，这意味着这些难题属于NP。然后，我们证明这些难题是NP完整的。对于某些特殊情况，我们提供多项式时间算法。最终，我们考虑了足以使所有实例可解决的实例的数量，并就填充垃圾箱的数量和垃圾箱的容量来提供非平凡的上和下限。
Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps are popularized. In these puzzles, we are given a set of bins filled with colored units, balls or water, and some empty bins. These puzzles allow us to move colored units from a bin to another when the colors involved match in some way or the target bin is empty. The goal of these puzzles is to sort all the color units in order. We investigate computational complexities of these puzzles. We first show that these two puzzles are essentially the same from the viewpoint of solvability. That is, an instance is sortable by ball-moves if and only if it is sortable by water-moves. We also show that every yes-instance has a solution of polynomial length, which implies that these puzzles belong to in NP. We then show that these puzzles are NP-complete. For some special cases, we give polynomial-time algorithms. We finally consider the number of empty bins sufficient for making all instances solvable and give non-trivial upper and lower bounds in terms of the number of filled bins and the capacity of bins.
