Average Case Complete Problems
Average Case Complete Problems
复制标题
DOI：
10.1137/0215020
复制
发表时间：
1986-02
期刊：
影响因子：
--
通讯作者：
L. Levin
中科院分区：
文献类型：
--
作者：
L. Levin
许多有趣的组合问题被发现是NP完全的。由于在最坏的情况下快速解决它们的希望微乎其微，研究人员寻找快速的算法，只是平均而言，这一问题对特定NP-完全问题的选择及其实例的概率分布是敏感的。其中一些任务很容易，另一些则不容易。但人们需要一种方法来区分“平均而言困难”的问题。这样的负面结果不仅可以节省“积极”的努力，而且还可以用于某些问题的难度经常被假设的领域(如密码学)。文献[1]证明了均匀分布实例的平铺问题不存在多项式平均算法，除非每个简单概率分布的NP问题都有多项式平均算法。
Many interesting combinatorial problems were found to be NP-complete. Since there is little hope to solve them fast in the worst case, researchers look for algorithms which are fast just “on average,” This matter is sensitive to the choice of a particular NP-complete problem and a probability distribution of its instances. Some of these tasks are easy and some not. But one needs a way to distinguish the “difficult on average” problems. Such negative results could not only save “positive” efforts but may also be used in areas (like cryptography) where hardness of some problems is a frequent assumption. It is shown in [1] that the Tiling problem with uniform distribution of instances has no polynominal “on average” algorithm, unless every NP-problem with every simple probability distribution has it.