<p>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 <a href="http://dl.acm.org/citation.cfm?id=237838">Ajtai's paper</a> and what came after it (works by Regev, Micciancio, Peikert,...).</p>

<p>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 <a href="http://www.google.com/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=3&amp;ved=0CCsQFjAC&amp;url=http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=7E76245F152751684D1D622BE251DF37?doi=10.1.1.42.406&amp;rep=rep1&amp;type=ps&amp;ei=jTHBTsqnFOTq2QXf__ixBQ&amp;usg=AFQjCNHMZSSk_QajpwTaGLnyMWNIGbgq_A&amp;sig2=dJfJAw___vqtZ9c19B6tYA">Feigenbaum and Fortnow</a>): (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). </p>

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

CC BY-SA 3.0
2011-11-14T15:28:29.663Z
2011-11-14T23:08:51.007Z
2011-11-14T23:08:51.007Z
Dana Moshkovitz
<p>This type of problem has been the subject of quite a bit of study. You can find references by googling <a href="http://en.wikipedia.org/wiki/Random_self-reducibility">random self-reducibility,</a> and the Wikipedia article is a good place to start reading. There are still a lot of associated open questions.</p>

CC BY-SA 3.0
2011-11-14T04:15:49.693Z
2011-11-14T04:15:49.693Z
Peter Shor 
<p>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?</p>

CC BY-SA 3.0
2011-11-13T18:59:31.290Z
[Random self-reducibility](http://en.wikipedia.org/wiki/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 
CC BY-SA 3.0
2011-11-14T00:50:32.827Z
@PeterShor comment -> answer ?
Suresh Venkat
<cc.complexity-theory><reductions><average-case-complexity>
Worst case to average case reductions
Anonymous
# Worst case to average case reductions

(Asked by: username_0 on 2011-11-13)

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?

**Tags:** cc.complexity-theory, reductions, average-case-complexity

> **Comments:**
> **username_1**: [Random self-reducibility](http://en.wikipedia.org/wiki/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.)  
> **username_2**: @PeterShor comment -> answer ?  

---

## 2 answers

### Answer by username_1 on 2011-11-14. Score: 18 | Accepted answer

This type of problem has been the subject of quite a bit of study. You can find references by googling [random self-reducibility,](http://en.wikipedia.org/wiki/Random_self-reducibility) and the Wikipedia article is a good place to start reading. There are still a lot of associated open questions.


---

### Answer by username_3 on 2011-11-14. Score: 15

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](http://dl.acm.org/citation.cfm?id=237838) 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](http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&ved=0CCsQFjAC&url=http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=7E76245F152751684D1D622BE251DF37?doi=10.1.1.42.406&rep=rep1&type=ps&ei=jTHBTsqnFOTq2QXf__ixBQ&usg=AFQjCNHMZSSk_QajpwTaGLnyMWNIGbgq_A&sig2=dJfJAw___vqtZ9c19B6tYA)): (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).


---

