Hardness of Minimal Symmetry Breaking in Distributed Computing