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?
$\begingroup$
$\endgroup$
2
-
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$– Peter ShorNov 13, 2011 at 18:59
-
1$\begingroup$ @PeterShor comment -> answer ? $\endgroup$– Suresh VenkatNov 14, 2011 at 0:50
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
answered Nov 14, 2011 at 4:15
$\begingroup$
$\endgroup$
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).
answered Nov 14, 2011 at 15:28