# Smoothed analysis in the Turing machine model

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?

• 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. Commented May 28 at 8:01
• @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$. Commented May 28 at 8:04