The algorithms I know for solving 3SAT typically have exponential run-time distributions which become wider in their PDF as the number of variables, $N$, increases. For the exponential distribution this specifically means that the relative variance, $var_{rel} = \frac{var(PDF)}{mean^2(PDF)}$, of the PDF with increasing $N$ is constant (exactly $var_{rel}(N)=1$ actually) and the kurtosis is constant as well.

Are there any algorithms whose relative variance in the PDF of the run-time distribution would be expected to decrease, specifically as $\sim \frac{1}{N}$, and/or where the kurtosis decreases?

This would seem intuitively strange to me since that would mean that the algorithm would become more "deterministic" (in the physics sense), but I want to make sure.

Is there a straightforward interpretation of what it would mean for a non-trivial, competitive algorithm to exhibit such a trait of $var_{rel}\sim \frac{1}{N}$ and decreasing kurtosis?


1 Answer 1


It is easy to come up with artificial examples of algorithms with this property. For instance:

  1. Enumerate all $2^N$ possible assignments of truth values and check if any of them are satisfiable.

  2. Pick a random number $T$ from some distribution, and do $T-2^N$ steps of no-ops.

Now it suffices to pick a distribution for $T$ such that $T$ has your desired property on the relative variance, and such that $T$ is always at least $2^N$. Such distributions are easy to find.

This indicates that the question you asked probably does not capture what you actually care about.

In real life, the variance of the running time probably doesn't isn't something we directly care about minimizing. Some examples of metrics that might plausibly matter: the expected running time, or the worst-case running time, or a value $t$ such that there is at least a $1-\epsilon$ probability that the running time will not exceed $t$, or any number of other variations along those lines.

  • 1
    $\begingroup$ It's not so much about trying to minimize the variance as it is about putting into context what it means for a non-trivial, competitive algorithm to exhibit such a trait of decreasing variance & kurtosis. $\endgroup$ Jul 11, 2022 at 18:28
  • $\begingroup$ @DanielPrimosch, OK. Well, I've answered the question you asked, and I'm not sure what more to say. Perhaps the question you asked doesn't capture what you really want to know. $\endgroup$
    – D.W.
    Jul 11, 2022 at 18:49
  • 1
    $\begingroup$ I've edited the question to better reflect why I'm asking. Thanks for the feedback $\endgroup$ Jul 11, 2022 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.