On the Computational Complexity of Partitioning …