Average-case complexity: Difference between revisions

Revision as of 17:36, 13 December 2018

Revision as of 14:47, 7 January 2019

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-complete problems have DistNP-complete versions.<ref name="livne06">N. Livne, "All Natural NPCNP-Complete Problems Have Average-Case Complete Versions," Computational Complexity, to(2010) appear19:477. Preliminary version in ECCC, TR06https://doi.org/10.1007/s00037-122, 2006.010-0298-9</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==