
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.
random 3-SAT, first moment method, existence-discovery separation, solver comparison, sensitivity exponent, computational budget
random 3-SAT, first moment method, existence-discovery separation, solver comparison, sensitivity exponent, computational budget
| 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 |
