Constraint Complexity and Solvability Phase Transition of the Sphere Packing Problem

The computational complexity of the sphere packing problem changes with constraint strength. Prior work [1-3] defined discrete constraint levels, proving that the general sphere packing is NP-complete, while a strongly constrained variant is constant-time solvable, yielding 1836. This paper studies the discrete constraint strength spectrum. We define four constraint levels: κ=0 (unconstrained, NP-complete); κ=1 (orthogonal tubular code, linear-time solvable, bounds 2118–2160); κ=2 (plus covering completeness, linear-time solvable, total angular circumference 918°); κ=3 (plus orbital closure condition, constant-time solvable, exact solution 1836). These four levels constitute a complete computational phase transition—each increase in constraint strength reduces computational complexity by one step. Constraint strength serves as an order parameter driving the problem from NP-complete to constant-time solvable. 1836 is the unique solution at the constraint saturation point, and is the global attractor in the constraint strength space. This paper, together with [1-3], completes the full characterization of the sphere packing problem from NP-complete to exactly solvable.