Locality Causes Tractability? An Intervention Study on the Variable-Interaction Radius in Geometric Random Satisfiability (Compact Version)
A widespread intuition holds that real-world computational problems are easy because their ``causes act locally'': when variables interact only within small neighbourhoods, constraint solvers should scale well. Observational evidence supports the intuition, but observation cannot separate locality from the many other regularities real instances carry. We translate the intuition into a falsifiable, interventional claim: holding the number of variables fixed, matching clause density relative to each radius's own threshold, and with clause-content statistics r-invariant by construction, varying \\emph{only} the radius $r$ within which clause variables are drawn from a 2-D torus should causally change CDCL solving difficulty. Three findings. \\emph{(i)}~The operational satisfiability boundary is not $r$-invariant: it lies below density 2.5 at $r=0.06$ and near the classical ${\\approx}4.3$ region by $r=0.22$ (a displacement of at least 1.7 density units) --- locality moves the sat/unsat boundary itself --- before becoming unmeasurable at $r\\ge 0.3$ under a $10^7$-conflict budget. \\emph{(ii)}~At density matched relative to each radius's own threshold, difficulty spans $3.4$ orders of magnitude across $r$ among decided instances (mean $\\log_{10}$ conflicts $1.45 \\to 4.86$ from $r=0.06$ to $0.22$), and $\\ge 4.5$ orders when budget-censored runs are counted at their lower bound; RM-ANOVA $F(8,216)=2808.5$, $p\\approx10^{-213}$; Jonckheere--Terpstra $p\\le 10^{-4}$ with FDR $q\\le 10^{-4}$; partial $\\eta^2 \\approx 0.99$. \\emph{(iii)}~A degree-preserving swap that destroys spatial locality while keeping every literal's occurrence count exactly fixed raises difficulty by $16$--$68\\times$ (Wilcoxon $p\\le 7\\times10^{-10}$) and flips the satisfiability status of 53 instance pairs; causal mediation attributes ${\\sim}94\\%$ of the radius effect to community-structure restructuring (ACME 3.06, bootstrap CI $[2.84, 3.37]$). Locality is not merely correlated with tractability --- under our controls it is the causal channel. All claims are scoped to $n=400$, direct CNF encodings, and CDCL-family solvers; we discuss what this does and does not say about P versus NP. Code, seeds, data, preregistration, and the full audit trail are public.
Authors
- Jin Song
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-09-15
- DOI
- https://doi.org/10.5281/zenodo.22777748
- Primary Topic
- Constraint Satisfaction and Optimization
- Type
- preprint