问题的最坏情况和平均情况有什么区别？

Question

我正在研究关于格上一些难题的归约。"；最坏情况到平均情况的减少"？例如，论文"；基于高斯测度的最坏情况到平均情况的约简"；给出了从最坏情况的INCGDD问题到平均情况的SIS问题的简化，这意味着什么？

Answer 1

如果存在平均在C时间内解决问题的算法，并且根据某种分布随机选择输入，则问题具有平均事例时间复杂性C。将其形式化很棘手，请参阅此处。

一个问题具有更差情况到平均情况的约简如果你可以显示以下内容：如果存在一个解决具有平均情况复杂度C的问题的算法，那么该算法也可以用于解决具有相同复杂度(模多项式因子(的最坏情况。