Structural vs Representational Rigidity in Constraint Satisfaction Problems: A Diagnostic Framework (With Implications for P vs NP)

Related Work: De Jesus, Elias. (2026). Geometric Rigidity, Solver Regimes, and Scale-Dependent Hardness: A Technical Note and Experimental Handoff. Zenodo. https://doi.org/10.5281/zenodo.18226432 This work develops and validates a diagnostic framework for separating intrinsic (structural) hardness from representational (observer-induced) hardness in constraint satisfaction problems (CSPs). We introduce a geometric notion of rigidity—the minimum resolution required to traverse a solution space—and show that this rigidity decomposes into two measurable components: one that persists under all symmetry collapses (structural) and one that vanishes when redundant differentiation is removed (representational). Through exhaustive experiments on small instances, we demonstrate that random 3-SAT near the satisfiability threshold is maximally differentiated: its solution space has trivial automorphism groups, exhibits zero rigidity reduction under symmetry quotienting, and remains rigid under changes of observer-defined metrics (probe-invariance). In contrast, structured CSPs (graph coloring, exact-k constraints, bipartite matching) exhibit large representational inflation, with rigidity collapsing by 37.5%–100% under symmetry quotienting. To connect geometry with algorithmic behavior, we introduce Symmetry-Breaking Efficiency (η), a solver-level metric that measures how effectively an algorithm exploits representational collapse. Empirical results show that modern SAT solvers are largely symmetry-blind: even when representational rigidity is maximal, solver-induced reduction is minimal. Random 3-SAT forms a structural hardness wall, where no representational shortcut exists. Finally, we establish probe-invariance as a criterion for intrinsic hardness: rigidity in random 3-SAT persists across Hamming, clause-weighted, and SAT-preserving geodesic metrics, behaving as a structural singularity rather than a measurement artifact. This framework reframes computational hardness as a question of irreducible differentiation versus removable projection, providing new experimental tools without making claims about $\mathsf{P}$ vs $\mathsf{NP}$.