Computational Complexity of the Sphere Packing Problem: NP-Completeness Conjecture and the Constraint-Complexity Spectrum

The sphere packing problem asks for the maximum number of points that can be placed on the unit sphere S² such that the pairwise distance is no less than a given value d. The exact value of this problem has remained unknown for over a century. This paper studies the computational complexity of this problem. We propose and argue for the following conjecture: for any fixed distance threshold d, the decision problem of whether there exist N points on S² with pairwise distance ≥ d is NP-complete. Evidence supporting this conjecture includes: the combinatorial explosion nature of the general sphere packing problem, its deep connection with a known NP-complete problem (determining the minimum distance of a general linear code), and the reduction framework from graph independent set to sphere packing presented in this paper. We further combine this conjecture with prior work on the constraint strength spectrum to provide a complete characterization of the computational phase transition of the sphere packing problem, from NP-complete (conjectured) to constant-time solvable. When no additional constraints are imposed, the problem is conjectured to be NP-complete; upon imposing the three-layer orthogonal great-circle tubular neighborhood constraint, it drops to linear time; upon further imposing covering completeness and the orbital closure condition, it drops to constant time, with the solution uniquely determined as 1836. This spectrum explains the inherent difficulty of the century-old sphere packing problem from the perspective of computational complexity and reveals the deep principle of constraint strength as a control parameter for computational phase transitions.