# Worst case to average case reductions

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?

• 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.) – Peter Shor Nov 13 '11 at 18:59
• @PeterShor comment -> answer ? – Suresh Venkat Nov 14 '11 at 0:50

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).