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?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.