Average-case complexity: Difference between revisions

Revision as of 00:12, 13 December 2013

Revision as of 01:03, 13 December 2013

Line 47:

==Reductions Between Distributional Problems==

Let (L,D) and (L',D') be two distributional problems. (L, D) average-case reduces to (L', D') (written $(L, D) ≤_AvgP (L', D')) if there is a function f that for every n, on input x can be computed in time polynomial in n and

#(Correctness) x ∈ L if and only if f(x) ∈ L'

Line 63:

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 &mu; is one for which there exists an &epsilon; > 0 such that for any x, &mu;(x) &le; 2^{-|x|^&epsilon;}.) 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>

==Applicatons==