<p>It is easy to come up with artificial examples of algorithms with this property.  For instance:</p>
<ol>
<li><p>Enumerate all <span class="math-container">$2^N$</span> possible assignments of truth values and check if any of them are satisfiable.</p>
</li>
<li><p>Pick a random number <span class="math-container">$T$</span> from some distribution, and do <span class="math-container">$T-2^N$</span> steps of no-ops.</p>
</li>
</ol>
<p>Now it suffices to pick a distribution for <span class="math-container">$T$</span> such that <span class="math-container">$T$</span> has your desired property on the relative variance, and such that <span class="math-container">$T$</span> is always at least <span class="math-container">$2^N$</span>.  Such distributions are easy to find.</p>
<p>This indicates that the question you asked probably does not capture what you actually care about.</p>
<p>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 <span class="math-container">$t$</span> such that there is at least a <span class="math-container">$1-\epsilon$</span> probability that the running time will not exceed <span class="math-container">$t$</span>, or any number of other variations along those lines.</p>

CC BY-SA 4.0
2022-07-11T18:28:31.143Z
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.
Daniel Primosch
CC BY-SA 4.0
2022-07-11T18:49:05.247Z
@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.
D.W.
CC BY-SA 4.0
2022-07-11T18:56:13.363Z
I've edited the question to better reflect why I'm asking. Thanks for the feedback
Daniel Primosch
CC BY-SA 4.0
2022-07-11T18:12:15.703Z
2022-07-11T18:12:15.703Z
D.W.
<p>The algorithms I know for solving 3SAT typically have exponential run-time distributions which become wider in their PDF as the number of variables, <span class="math-container">$N$</span>, increases. For the exponential distribution this specifically means that the relative variance, <span class="math-container">$var_{rel} = \frac{var(PDF)}{mean^2(PDF)}$</span>, of the PDF with increasing <span class="math-container">$N$</span> is constant (exactly <span class="math-container">$var_{rel}(N)=1$</span> actually) and the kurtosis is constant as well.</p>
<p>Are there any algorithms whose relative variance in the PDF of the run-time distribution would be expected to decrease, specifically as <span class="math-container">$\sim \frac{1}{N}$</span>, and/or where the kurtosis decreases?</p>
<p>This would seem intuitively strange to me since that would mean that the algorithm would become more &quot;deterministic&quot; (in the physics sense), but I want to make sure.</p>
<p>Is there a straightforward interpretation of what it would mean for a non-trivial, competitive algorithm to exhibit such a trait of <span class="math-container">$var_{rel}\sim \frac{1}{N}$</span> and decreasing kurtosis?</p>

<ds.algorithms>
Do reasonably competitive 3SAT algorithms ever have shrinking run-time distributions when measured as a probability density function?
Daniel Primosch
# Do reasonably competitive 3SAT algorithms ever have shrinking run-time distributions when measured as a probability density function?

(Asked by: username_0 on 2022-07-11)

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?

**Tags:** ds.algorithms


---

## 1 answers

### Answer by username_1 on 2022-07-11. Score: 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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: @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.  
> **username_0**: I've edited the question to better reflect why I'm asking. Thanks for the feedback  

---

