Computational Complexity of the Sphere Packing Problem: NP-Completeness Proof

The sphere packing problem asks for the maximum number of points that can be placed on the unit sphere S² such that the pairwise spherical distance is no less than a given value d. The exact value for this problem has remained unknown for over a century. This paper studies the computational complexity of this problem. We rigorously prove that, for any fixed distance threshold d, the decision problem of whether there exist N points on S² with pairwise distance ≥ d is NP-complete. The proof employs a polynomial-time reduction from the graph independent set problem to sphere packing. Given an arbitrary graph G, we construct a set of points on the sphere such that the independent sets of G are in one-to-one correspondence with the feasible solutions of the sphere packing. This reduction can be carried out in polynomial time and does not rely on any additional geometric or physical assumptions. The conclusion of this paper explains the inherent difficulty of the century-old sphere packing problem from the perspective of computational complexity: its exact solution is NP-hard, and unless P=NP, no polynomial-time exact algorithm exists. Combined with prior work on the constraint strength spectrum, this completes the full complexity characterization of the sphere packing problem, from NP-complete to constant-time solvable.