Do reasonably competitive 3SAT algorithms ever have shrinking run-time distributions when measured as a probability density function?

Question

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?

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.