Orbit-Collapse Complexity: A Symmetry-Based Lens on P, NP, and Structured Cores
Discuss this preprint
Start a discussion What are Sciety discussions?Listed in
This article is not in any list yet, why not save it to one of your lists.Abstract
We introduce \emph{Orbit-Collapse Complexity} (OCC), a symmetry-aware framework that explains when NP problems behave as polynomial-time problems. If instances canonically collapse to \emph{polynomially many types} under an explicit group action, with polytime canonicalization and per-type solvers, the whole language is in P. We quantify ``how much structure'' a problem exhibits via (i) \emph{orbit coverage} (fraction of solution orbits captured by a P-core), (ii) a \emph{type-growth exponent} (asymptotic number of canonical types), and (iii) an \emph{orbit-compressibility} index (stabilizer size). We enforce hardness beyond cores via \emph{Layer-Respecting Reductions} (LRR) that preserve or raise layer depth. For Sudoku we give closed formulas for separable classes, a degree-4 certificate for the bi-affine layer, and Pólya blueprints for piecewise families. The result is a measurable frontier between P-like cores and genuinely hard remainder, offering a unifying lens across SAT, Graph Coloring, TSP, IP, and Sudoku.