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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
preprint

Locality Causes Tractability? An Intervention Study on the Variable-Interaction Radius in Geometric Random Satisfiability (Compact Version)

Jin Song
Zenodo (CERN European Organization for Nuclear Research)
Constraint Satisfaction and Optimization
preprint

Locality Causes Tractability? An Intervention Study on the Variable-Interaction Radius in Geometric Random Satisfiability (Compact Version)

Jin Song
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Constraint Satisfaction and Optimization
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Locality Causes Tractability? An Intervention Study on the Variable-Interaction Radius in Geometric Random Satisfiability (Compact Version) — Jin Song · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS