Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > AVERAGE CASE COMPLETE PROBLEMS:
Reports tagged with average case complete problems:
TR06-122 | 20th September 2006
Noam Livne

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

Revisions: 1

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
more >>>

ISSN 1433-8092 | Imprint