Revision as of 01:03, 13 December 2013 edit Aramiann (talk \| contribs) 3 edits m corrected two typos ← Previous edit		Revision as of 23:09, 13 December 2013 edit undo Aramiann (talk \| contribs) 3 edits m Corrected a reference and a factual error Next edit →
Line 42: A distributional problem (L, D) is in the complexity class AvgP if there is an efficient average-case algorithm for L, as defined above. The class AvgP is occasionally called distP in the literature.<ref name="ab09"/> A distributional problem (L, D) is in the complexity class distNP if L is in NP and D is P-computable. ~~(or~~When L is in NP and D is P-samplable, (L, D) belongs to sampNP.<ref name="ab09"/> Together, AvgP and ~~DistNP~~distNP define the average-case analogues of P and NP, respectively.<ref name="ab09"/> ==Reductions Between Distributional Problems== Line 55: ===DistNP-Complete Problems=== The average-case analogue to NP-completeness is distNP-completeness. A distributional problem (L', D') is distNP-complete if (L', D') is in distNP and for every (L, D) in distNP, (L, D) is average-case reducible to (L', D').~~\cite{~~<ref name="ab09}" /> An example of a distNP-complete problem is the Bounded Halting Problem, BH, defined as follows:

Average-case complexity: Difference between revisions