Smoothed analysis of the Partition problem

Question

I am studying smoothed analysis and trying to apply it to the Partition decision problem: given $n$ real numbers with a sum of $2 S$, decide whether there exists a subset with a sum of exactly $S$.

The common definition of the smoothed runtime complexity of an algorithm is: 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]$.

If I apply this definition to the Partition problem, it seems that for any $\sigma > 0$, the runtime complexity is $O(1)$, since for any random noise that is added to the original numbers - no matter how small - the answer is "no" with probability 1.

This is strange, since in the more common examples of smoothed analysis, the runtime complexity depends on $\sigma$, and here it does not.

Is there something I misunderstood? What is the smoothed runtime complexity of Partition?

Answer 1

Smoothed analysis, as I have seen it, has typically been used for analyzing optimization problems, not decision problems. The partition problem is a decision problem, which introduces the challenge you mentioned. Perhaps one could consider the optimization variant of the partition problem: given $n$ numbers with a sum of $2S$, find the subset whose sum is as close to $S$ as possible. I don't know whether the smoothed complexity of that optimization problem would be interesting or illuminating, but it eliminates the problems you articulate in the question.