Are there problems whose average case complexity is the same as their worst case complexity? What are the underlying properties of these problems that makes reducing the worst case to the average case possible?

  • 10
    $\begingroup$ Random self-reducibility (That's more of a definition than an underlying property, but I suspect the Wikipedia article will give you a good start on figuring out what you want to know.) $\endgroup$ Nov 13 '11 at 18:59
  • 1
    $\begingroup$ @PeterShor comment -> answer ? $\endgroup$ Nov 14 '11 at 0:50

This type of problem has been the subject of quite a bit of study. You can find references by googling random self-reducibility, and the Wikipedia article is a good place to start reading. There are still a lot of associated open questions.


The Wikipedia entry that Peter linked to mentions a few important examples of problems that have worst-case to average case reductions, like the permanent. Shortest vector problem (as well as related lattice problems) is another important example, see Ajtai's paper and what came after it (works by Regev, Micciancio, Peikert,...).

One of the only general observations we have regarding problems with worst-case to average-case reduction is the following (started with the work of Feigenbaum and Fortnow): (At least for non-adaptive reductions,) these problems are not likely to be complete to classes that are (probably) not closed under complement (e.g., they are not likely to be NP-complete).

Other than that, you can find problems with worst-case-to-average-case reductions of various complexities, e.g., in $NP \cap coNP$ (lattice problems and other crypto problems) and in #P (permanent).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.