All Natural NPC Problems Have Average-Case Complete Versions
Noam Livne · 2006
In 1984 Levin put forward a suggestion for a theory of average case complexity. In this theory a problem, called a distributional problem, is defined as a pair consisting of a decision problem and a probability distribution over the instances. Introducing adequate notions of ”efficiency-onaverage”, simple distributions and efficiency-on-average preserving reductions, Levin developed a theory analogous to the theory of N P-completeness. In particular, he showed that there exists a simple distributional problem that is complete under these reductions. But since then very few distributional problems were shown to be complete in this sense. In this paper we show a simple sufficient condition for an N P-complete decision problem to have a distributional version that is complete under these reductions (and thus to be ”hard on the average ” with respect to some simple probability distribution). Apparently all known N P-complete decision problems meet this condition.