Powered by OpenAIRE graph
Found an issue? Give us feedback
ZENODOarrow_drop_down
ZENODO
Preprint . 2026
License: CC BY
Data sources: Datacite
ZENODO
Preprint . 2026
License: CC BY
Data sources: Datacite
versions View all 2 versions
addClaim

Predicting Computational Cost from the Structural Parameter δ: Separating Existence from Discovery in Random 3-SAT

Authors: Sunagawa, Akihito;

Predicting Computational Cost from the Structural Parameter δ: Separating Existence from Discovery in Random 3-SAT

Abstract

Whether a solution exists and whether an algorithm can find it are distinct questions governed by different mechanisms. In random 3-SAT, the first moment method gives P(SAT) ≈ N_eff · e^(−δ), where δ = αn|ln(7/8)| is a reparameterization of the clause density (the exponent in the first moment method). This characterizes existence but says nothing about discovery. We introduce the computational budget μ (solver operations) and ask: can the conditional success probability P(found|SAT) be multiplicatively decomposed as a function of μ/μ_c(δ)? Experiments on three solver families (CDCL, WalkSAT, Random search) across n = 100–300 variables, α = 3.0–4.0, yield three findings. (1) Median runtime scales as μ_c ∝ e^(cδ), where the sensitivity exponent c is solver-dependent: c ≈ 0.24 (CDCL), c ≈ 0.21 (WalkSAT), c = 1.0 (Random, exact) in the floor-free regime α ≥ 3.5. (2) The ratio μ/μ_c is a valid normalizing variable: both solvers transition monotonically near μ/μ_c = 1, but transition shapes differ by 14–15%. (3) The ordering c_CDCL > c_WalkSAT is robust across problem sizes, though both estimates show moderate n-dependence. The parameter δ governs both existence (c = 1, mathematical identity) and discovery (c < 1, algorithm-dependent), but with qualitatively different sensitivities. Notably, c measures sensitivity to δ, not efficiency: WalkSAT has the smallest c but the largest absolute cost, meaning low sensitivity can arise from ignoring structure rather than exploiting it.

Keywords

random 3-SAT, first moment method, existence-discovery separation, solver comparison, sensitivity exponent, computational budget

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!