Average-case complexity: Difference between revisions

Revision as of 09:38, 21 August 2015

Revision as of 17:51, 9 October 2016

Line 65:

In his original paper, Levin showed an example of a distributional tiling problem that is average-case NP-complete.<ref name="levin86"/> A survey of known distNP-complete problems is available online.<ref name="wangsurvey"/>

One area of active research involves finding new distNP-complete problems. However, finding such problems can be complicated due to a result of Gurevich which shows that any distributional problem with a flat distribution cannot be distNP-complete unless [[EXP]] = [[NEXP]].<ref name="gur87">Y. Gurevich, "Complete and incomplete randomized NP problems", Proc. 28th Annual Symp. on Found. of Computer Science, IEEE (1987), pp. 111–117.</ref> (A flat distribution μ is one for which there exists an ε > 0 such that for any x, μ(x) ≤ 2^{-−|x|^ε}.) A result by Livne shows that all natural NP problems have DistNP-complete versions.<ref name="livne06">N. Livne, "All Natural NPC Problems Have Average-Case Complete Versions," Computational Complexity, to appear. Preliminary version in ECCC, TR06-122, 2006.</ref> However, the goal of finding a natural distributional problem that is DistNP-complete has not yet been achieved.<ref name="gol97">O. Goldreich, "Notes on Levin's theory of average-case complexity," Technical Report TR97-058, Electronic Colloquium on Computational Complexity, 1997.</ref>

==Applications==