平滑分析分区问题

Question

我正在学习平滑分析并试图将其应用于分区决策问题：给定 $ n $ 使用 $ 2 s $ 的实数，决定是否存在总和的子集完全 $ s $ 。

算法的平滑运行时复杂度的共同定义是： 给定 $ n $ 和 $ \ sigma $ ，算法的平滑运行时间是最大的大小 $ n $ ，在输入时运行时的运行时扰动何时扰动 $ \ sigma $ ，例如通过向每个输入从正常分布中随机选择的数字，使用标准偏差 $ \ sigma $ ，或者从带支持 $ [0，\ sigma] $ 。

如果我将这个定义应用于分区问题，似乎是任何 $ \ sigma> 0 $ ，运行时复杂性是 $ o（1）$ ，因为对于添加到原始数字的任何随机噪声 - 无论多么小 - 答案为“否”，概率为1。< / p>

这是奇怪的，因为在平滑分析的更常见示例中，运行时复杂性取决于 $ \ sigma $ ，在这里没有。

我误解了什么吗？分区的平滑运行时复杂性是多少？

Answer 1

平滑分析，正如我所见，通常已被用于分析优化问题，而不是决策问题。分区问题是一个决策问题，介绍了您提到的挑战。也许可以考虑分区的优化变体问题：给定 $ n $ 数字，其中一个 $ 2s $ ，找到其总和与 $ s $ s $ 的子集。我不知道那个优化问题的平滑复杂性是否会有趣或照明，但它消除了您在问题中发表的问题。