Content deleted Content added
→DistNP-complete problems: mention a distribution. |
|||
Line 79:
==Other results==
[[Yao's principle]], from a 1978 paper by [[Andrew Yao]], shows that for broad classes of computational problems, average-case complexity for a hard input distribution and a deterministic algorithm adapted to that distribution is the same thing as expected complexity for a fast randomized algorithm and its worst-case input.<ref>{{citation
| last = Yao | first = Andrew | author-link = Andrew Yao
| contribution = Probabilistic computations: Toward a unified measure of complexity
| doi = 10.1109/SFCS.1977.24
| pages = 222–227
| title = Proceedings of the 18th IEEE Symposium on Foundations of Computer Science (FOCS)
| year = 1977}}</ref>
In 1990, Impagliazzo and Levin showed that if there is an efficient average-case algorithm for a {{math|'''distNP'''}}-complete problem under the uniform distribution, then there is an average-case algorithm for every problem in {{math|'''NP'''}} under any polynomial-time samplable distribution.<ref name="imp90">R. Impagliazzo and L. Levin, "No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random," in Proceedings of the 31st IEEE Sympo- sium on Foundations of Computer Science, pp. 812–821, 1990.</ref> Applying this theory to natural distributional problems remains an outstanding open question.<ref name="bog06"/>
| |||