Average-Case Computations — Comparing AvgP, HP, and Nearly-P
Arfst Nickelsen, Birgit Schelm · 2005
We examine classes of distributional problems defined in terms of polynomial-time decision algorithms with bounded error probability. The class AvgP (Levin, 1984) has been characterized by Impagliazzo (1995) using polynomial-time algorithm schemes with benign faults. The class HP extends AvgP by allowing malign faults instead of benign faults. The class AvgHP in turn extends HP by allowing running times to be polynomial on average instead of bounded by a polynomial. Polynomial-time algorithms that decide membership for words of length n with an error probability less than F(n) for some function F lead to the classes F(n)-ErrP (Schindelhauer and Jakoby, 1999). The class dist-nearly-P = /spl cap//sub k/spl ges/1/(1/n/sup k/)-ErrP is an instance of the 'nearly'-classes as introduced by Yamakami (1997). We call a distribution /spl mu/ fair if /spl mu/(n) /spl ges/ 1/p(n) for some polynomial p(n). We prove: 1) The inclusion AvgP /spl sube/ HP is strict. 2) AvgHP equals HP. 3) Problems from HP with fair distributions are in dist-nearly-P. One cannot substantially improve this result. There are problems in AvgP with fair distributions which are not in (1/g(n))-ErrP for every super-polynomial function g(n). And there are problems in AvgP with /spl mu/(n) = 1/g(n) for a super-polynomial function g(n) which are not in dist-nearly-P.