ECCC-Report TR06-122https://eccc.weizmann.ac.il/report/2006/122Comments and Revisions published for TR06-122en-usThu, 04 Jan 2007 00:00:00 +0200
Revision 1
| All Natural NPC Problems Have Average-Case Complete Versions |
Noam Livne
https://eccc.weizmann.ac.il/report/2006/122#revision1In 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-on-average", simple distributions and efficiency-on-average preserving reductions, Levin developed a theory analogous to the theory of NP-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 NP-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 NP-complete decision problems meet this condition.
Thu, 04 Jan 2007 00:00:00 +0200https://eccc.weizmann.ac.il/report/2006/122#revision1
Paper TR06-122
| All Natural NPC Problems Have Average-Case Complete Versions |
Noam Livne
https://eccc.weizmann.ac.il/report/2006/122In 1984 Levin put forward a suggestion for a theory of {\em average
case complexity}. In this theory a problem, called a {\em
distributional problem}, is defined as a pair consisting of a
decision problem and a probability distribution over the instances.
Introducing adequate notions of simple distributions and average
case preserving reductions, Levin developed a theory analogous to
the theory of NP-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 very
simple sufficient condition for an NP-complete decision problem to
have a distributional version that is complete under these
reductions. Apparently all known NP-complete decision problems meet
this condition.
Wed, 20 Sep 2006 16:02:31 +0300https://eccc.weizmann.ac.il/report/2006/122