科研之友
微信
新浪微博
Facebook
分享链接
摘要
The theory of average case complexity studies the expected complexity of computational tasks under various specific distributions on the instances, rather than their worst case complexity. Thus, this theory deals with distributional problems, defined as pairs each consisting of a decision problem and a probability distribution over the instances. While for applications utilizing hardness, such as cryptography, one seeks an efficient algorithm that outputs random instances of some problem that are hard for any algorithm with high probability, the resulting hard distributions in these cases are typically highly artificial, and do not establish the hardness of the problem under "interesting" or "natural" distributions. This paper studies the possibility of proving generic hardness results (i.e., for a wide class of NP-complete problems), under "natural" distributions. Since it is not clear how to define a class of "natural" distributions for general NP-complete problems, one possibility is to impose some strong computational constraint on the distributions, with the intention of this constraint being to force the distributions to "look natural". Levin, in his seminal paper on average case complexity from 1984, defined such a class of distributions, which he called P-computable distributions. He then showed that the NP-complete Tiling problem, under some P-computable distribution, is hard for the complexity class of distributional NP problems (i.e. NP with P-computable distributions). However, since then very few NP-complete problems (coupled with P-computable distributions), and in particular " natural" problems, were shown to be hard in this sense. In this paper we show that all natural NP-complete problems can be coupled with P-computable distributions such that the resulting distributional problem is hard for distributional NP.
- 出版日期2010-12
