1.Previous
3.Next

These two formulations, while similar, are not equivalent. If a distribution is -computable it is also -samplable, but the converse is not true if {{math != .

AvgP and distNP

A distributional problem is in the complexity class if there is an efficient average-case algorithm for , as defined above. The class is occasionally called in the literature.

A distributional problem is in the complexity class if is in and is -computable.

1.Previous
3.Next