Contested Cluster Selectors: Local Ambiguity, Normal Forms, and Backtracking Cost in Random Constraint Satisfaction

Abstract

Abstract

We introduce and empirically investigate \emph{contested cluster selectors} (\CCS): variables that are non-backbone, carry information about solution-cluster identity, and are repeatedly but unreliably forced by local propagation during backtracking search. In instrumented \DPLL{} experiments on random 3-\SAT{} near the empirical satisfiability threshold and on near-optimal random \VC{} instances, a small number of such variables accounts for a large fraction of observed backtracking cost. Pinning two or three high-contestedness variables to solution-consistent values reduces backtracking by 70--80\% on the reference instances studied, and a static degree--polarity metric yields a simple $2^k$ enumeration heuristic with a reported $3.7\times$ speedup over baseline \DPLL{} at $n=50$. A polynomial control experiment on random 3-\XORSAT{} sharpens the interpretation. Gaussian elimination exposes the true affine selector coordinates, whereas \DPLL{} churn concentrates on pivot variables chosen in a poor coordinate system. Thus clustering and non-backbone status are not enough: the empirical hardness signal is \emph{local contestation} that remains after available polynomial-time normal forms. We formalize this distinction through safe coordinate exposers and the \emph{unavoidable contested selector cost} (\UCSC). We also prove an ordered single-pass eraser-memory lower bound: any ordered \FERAM{} that recovers a $k$-bit cluster label from a distribution with residual min-entropy $k-η$ using $S$ bits succeeds with probability at most $2^{S+η-k}$. The paper positions \CCS/\UCSC{} as a structural program connecting backdoors, solution-space geometry, low-degree barriers, and Schaefer-style algebraic normal forms. We do not claim a proof of $P\ne NP$; rather, we isolate the normal-form barrier that any such extension would need to overcome.