Sliding Cubes in Parallel

The work studies a “sliding cube” model of programmable matter in three dimensions, where many identical cube modules must move from one connected shape to another. The authors require that the overall structure stays connected via a backbone during the reconfiguration, and they measure efficiency by the makespan: how many parallel move steps are used. They prove that deciding whether a valid reconfiguration sequence exists is NP-hard, even under strong restrictions like constant makespan and only a constant-size difference between the start and end shapes. They also show that determining whether the best makespan is 1 or 2 is NP-hard. Beyond hardness results, the paper outlines an input-sensitive algorithm that is asymptotically worst-case optimal, but in the worst case the makespan can grow as O(n) due to the bounding box of the configurations.