Sorting Balls and Water: Equivalence and Computational Complexity
Sorting Balls and Water: Equivalence and Computational Complexity
复制标题
DOI：
10.4230/lipics.fun.2022.16
复制
发表时间：
2022-02
期刊：
影响因子：
--
通讯作者：
Takehiro Ito;J. Kawahara;S. Minato;Y. Otachi;Toshiki Saitoh;Akira Suzuki;Ryuhei Uehara;T. Uno;Katsuhisa Yamanaka;Ryo Yoshinaka
中科院分区：
文献类型：
--
作者：
Takehiro Ito;J. Kawahara;S. Minato;Y. Otachi;Toshiki Saitoh;Akira Suzuki;Ryuhei Uehara;T. Uno;Katsuhisa Yamanaka;Ryo Yoshinaka
多年来人们已经研究了各种形式的排序问题。最近流行两种排序益智应用程序。在这些谜题中，我们会得到一组装满彩色单元、球或水的箱子，以及一些空箱子。当涉及的颜色以某种方式匹配或目标箱为空时，这些谜题允许我们将彩色单元从一个箱移动到另一个箱。这些谜题的目标是按顺序对所有颜色单位进行排序。我们研究这些难题的计算复杂性。我们首先证明，从可解性的角度来看，这两个难题本质上是相同的。也就是说，当且仅当一个实例可以通过水移动排序时，它才可以通过球移动排序。我们还表明，每个“是”实例都有一个多项式长度的解，这意味着这些谜题属于 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.