Distance from Structure: Hidden Forcing Across Nine Random Constraint Families, the Local/Global Split, and a Toolkit-Relative Measure of How Far a Problem Sits from the Structure Distinctness Needs

A pre-registered study ran 231,000 random instances of nine constraint families (3-SAT, 4-SAT, NAE-3SAT, 3-coloring, 3-XOR-SAT, 2-SAT, Hamiltonian path, Hamiltonian cycle and perfect matching), with every rule frozen before an instance existed and the analysis run once. Near the satisfiability threshold, more of the decisions along a reference search are forced, in every family, and more of the forced decisions are hidden from unit propagation. Where the threshold is set by the global organization of the solutions, the transition window narrows with size and, wherever propagation leaves anything hidden, hidden forcing grows with size; where the threshold is set by a bounded local obstruction, neither happens. 3-XOR-SAT read as flat only because its hidden share was already near 1; on scales without that ceiling it grows as fast as the NP-complete families. Its forcing is hidden from unit propagation and visible to Gaussian elimination, so hidden forcing is a distance from a toolkit of one method. The note then defines the distance from structure: a function of a problem that is zero when a known method family captures the problem and otherwise says how far the problem sits from the structure those families reach, measured against a toolkit the definition names, with algebra counted, one rule for every problem, and a stated behavior under reductions. Intended uses are choosing a solver, predicting in advance where an AI model will fail on a constraint-type task, and measuring a cipher's exposure to algebraic attack. A confirmatory study on fresh instances is running; version 2 will report it.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-06
DOI
https://doi.org/10.5281/zenodo.24020904
Primary Topic
Constraint Satisfaction and Optimization
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Distance from Structure: Hidden Forcing Across Nine Random Constraint Families, the Local/Global Split, and a Toolkit-Relative Measure of How Far a Problem Sits from the Structure Distinctness Needs

Brian Spargur
Zenodo (CERN European Organization for Nuclear Research)
Constraint Satisfaction and Optimization
preprint

Distance from Structure: Hidden Forcing Across Nine Random Constraint Families, the Local/Global Split, and a Toolkit-Relative Measure of How Far a Problem Sits from the Structure Distinctness Needs

Brian Spargur
preprint en

Abstract

A pre-registered study ran 231,000 random instances of nine constraint families (3-SAT, 4-SAT, NAE-3SAT, 3-coloring, 3-XOR-SAT, 2-SAT, Hamiltonian path, Hamiltonian cycle and perfect matching), with every rule frozen before an instance existed and the analysis run once. Near the satisfiability threshold, more of the decisions along a reference search are forced, in every family, and more of the forced decisions are hidden from unit propagation. Where the threshold is set by the global organization of the solutions, the transition window narrows with size and, wherever propagation leaves anything hidden, hidden forcing grows with size; where the threshold is set by a bounded local obstruction, neither happens. 3-XOR-SAT read as flat only because its hidden share was already near 1; on scales without that ceiling it grows as fast as the NP-complete families. Its forcing is hidden from unit propagation and visible to Gaussian elimination, so hidden forcing is a distance from a toolkit of one method. The note then defines the distance from structure: a function of a problem that is zero when a known method family captures the problem and otherwise says how far the problem sits from the structure those families reach, measured against a toolkit the definition names, with algebra counted, one rule for every problem, and a stated behavior under reductions. Intended uses are choosing a solver, predicting in advance where an AI model will fail on a constraint-type task, and measuring a cipher's exposure to algebraic attack. A confirmatory study on fresh instances is running; version 2 will report it.

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.

Laika access coming soon