__
Revision #1 to TR06-122 | 4th January 2007 00:00
__
#### All Natural NPC Problems Have Average-Case Complete Versions

**Abstract:**
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-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.

__
TR06-122 | 20th September 2006 00:00
__

#### All Natural NPC Problems Have Average-Case Complete Versions

TR06-122
Authors:

Noam Livne
Publication: 20th September 2006 16:02

Downloads: 1764

Keywords:

**Abstract:**
In 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.