Sorting Balls and Water: Equivalence and Computational Complexity

Paper

Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, Ryo Yoshinaka - Sorting Balls and Water

Setup

• Bins colored with some units (balls or water) and the goal is to sort them.
• Each bin works as a stack.
• $hn$ balls, $n$ bins of capacity $h$ and $k$ empty bins.
• Balls need to be sorted in a move onto empty bins or balls of the same color.
• Water is very similar.

Results

• Water and Ball are actually equivalent.
• They are NP-complete.
• Are solvable in $h^n$ time.

Some Proof notes

• Reduction from 3 Partition.
• 3 Partition:
  • Given $a_1,\dots, a_{3m}$ with $\sum_{i} a_i = mB$.
  • $B/4 < a_i B/2$.
  • Is there a partition into subsets $A_1,\dots, A_m$ such that $\sum_{i\in A_j} a_i = B$?
• First direction: 3part -> water
  • We construct the following coloring from a 3 partition set:
  • Top contains only red and rest is blue.
  • From here we have an empty container and can fill it with the first set. Then compact and continue with the next set.
• Other direction by membership.