Orbit-Collapse Complexity: A Symmetry-Based Lens on P, NP, and Structured Cores

Read the full article See related articles

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.
Log in to save this article

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.

Article activity feed