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?
