<p>It seems that most research on smoothed analysis focuses on the analysis of algorithms in practice. The only work concerning the bit model I can find is Bläser and Manthey [1]. A relevant work is due to Beier and Vöcking [2], the main result of which states that a binary optimization problem is solvable in expected pseudo-polynomial time if and only if it is solvable in smoothed polynomial time.</p>
<p>[1]: Smoothed complexity theory. <a href="https://arxiv.org/pdf/1202.1936" rel="nofollow noreferrer">https://arxiv.org/pdf/1202.1936</a>.</p>
<p>[2]: Typical properties of winners and losers in discrete optimization.</p>

CC BY-SA 4.0
2024-05-31T15:16:16.160Z
Thanks! I also found this: https://en.wikipedia.org/wiki/Generic-case_complexity which presents a related but different model.
Erel Segal-Halevi
CC BY-SA 4.0
2024-05-29T11:37:56.700Z
2024-05-29T11:43:25.217Z
2024-05-29T11:43:25.217Z
Recursion
<p><a href="https://en.wikipedia.org/wiki/Smoothed_analysis" rel="nofollow noreferrer">Smoothed analysis</a> is usually defined using real numbers: given <span class="math-container">$n$</span> and <span class="math-container">$\sigma$</span>, the smoothed runtime of an algorithm is the maximum, over all inputs of size <span class="math-container">$n$</span>, of the runtime on the input when it is perturbed by a perturbation of size <span class="math-container">$\sigma$</span>, e.g. by adding to each input a number selected randomly from a normal distribution with standard deviation  <span class="math-container">$\sigma$</span>, or from any distribution with support <span class="math-container">$[0,\sigma]$</span>.</p>
<p>Are there works that try to define smoothed runtime complexity on the pure Turing machine model, where only strings of bits are allowed? For example, one could consider the following definitions:</p>
<ul>
<li>The smoothed runtime complexity is the maximum, over all inputs of size <span class="math-container">$n$</span>, of the <em>avergae</em> runtime on the input when some <span class="math-container">$k \in O(\log n)$</span> bits are changed independently at random.</li>
<li>An algorithm runs in smoothed polynomial time if for every input <span class="math-container">$x$</span> of size <span class="math-container">$n$</span>, it is possible to change some <span class="math-container">$k \leq \log(n)$</span> bits such that the algorithm runs in polynomial time on the new input <span class="math-container">$x'$</span>.</li>
</ul>
<p>Are there research works that develop similar ideas?</p>

CC BY-SA 4.0
2024-05-28T08:01:26.963Z
it's not clear what you mean in the first definition: the runtime of a TM is defined as the worst case for all inputs of size n, so a random perturbation does not matter. Even in the case of average complexity it seems adding a perturbation would not change the average.
Denis
CC BY-SA 4.0
2024-05-28T08:04:34.230Z
@Denis the first definition was missing the word "average"; I fixed it. Suppose you get an input $x$ of size $n$. You change some $k$ bits at random, and then run the algorithm and measure the run-time. You do this many times, each time with a different randomization, and measure the *average* run-time across all random perturbations. This is the smoothed runtime on input $x$. Now, you take the worst-case smoothed runtime over all inputs of size $n$.
Erel Segal-Halevi
<cc.complexity-theory><reference-request><turing-machines><smoothed-analysis>
Smoothed analysis in the Turing machine model
Erel Segal-Halevi
# Smoothed analysis in the Turing machine model

(Asked by: username_0 on 2024-05-28)

[Smoothed analysis](https://en.wikipedia.org/wiki/Smoothed_analysis) is usually defined using real numbers: given $n$ and $\sigma$, the smoothed runtime of an algorithm is the maximum, over all inputs of size $n$, of the runtime on the input when it is perturbed by a perturbation of size $\sigma$, e.g. by adding to each input a number selected randomly from a normal distribution with standard deviation $\sigma$, or from any distribution with support $[0,\sigma]$.

Are there works that try to define smoothed runtime complexity on the pure Turing machine model, where only strings of bits are allowed? For example, one could consider the following definitions:

* The smoothed runtime complexity is the maximum, over all inputs of size $n$, of the *avergae* runtime on the input when some $k \in O(\log n)$ bits are changed independently at random.
* An algorithm runs in smoothed polynomial time if for every input $x$ of size $n$, it is possible to change some $k \leq \log(n)$ bits such that the algorithm runs in polynomial time on the new input $x'$.

Are there research works that develop similar ideas?

**Tags:** cc.complexity-theory, reference-request, turing-machines, smoothed-analysis

> **Comments:**
> **username_1**: it's not clear what you mean in the first definition: the runtime of a TM is defined as the worst case for all inputs of size n, so a random perturbation does not matter. Even in the case of average complexity it seems adding a perturbation would not change the average.  
> **username_0**: @username_1 the first definition was missing the word "average"; I fixed it. Suppose you get an input $x$ of size $n$. You change some $k$ bits at random, and then run the algorithm and measure the run-time. You do this many times, each time with a different randomization, and measure the *average* run-time across all random perturbations. This is the smoothed runtime on input $x$. Now, you take the worst-case smoothed runtime over all inputs of size $n$.  

---

## 1 answers

### Answer by username_2 on 2024-05-29. Score: 2 | Accepted answer

It seems that most research on smoothed analysis focuses on the analysis of algorithms in practice. The only work concerning the bit model I can find is Bläser and Manthey [1]. A relevant work is due to Beier and Vöcking [2], the main result of which states that a binary optimization problem is solvable in expected pseudo-polynomial time if and only if it is solvable in smoothed polynomial time.

[1]: Smoothed complexity theory. <https://arxiv.org/pdf/1202.1936>.

[2]: Typical properties of winners and losers in discrete optimization.

> **Comments:**
> **username_0**: Thanks! I also found this: https://en.wikipedia.org/wiki/Generic-case_complexity which presents a related but different model.  

---

