On the theory of average case complexity (Q1190984)

The paper takes the next step in developing the theory of average case complexity initiated by L . A. Levin. A distributional decision problem is a pair \((D,\mu)\) where \(D\) is the set of strings and \(\mu\) is a (distribution) function from strings to the unit interval \([0,1]\). Most of the work deals with the class \(DistNP\) which consists of all problems (\(D,\mu)\) where \(D\in NP\) and \(\mu\) is computable in polynomial time. A distributional problem \((D,\mu)\) is an Average-\(P\) if there exists an algorithm \(A\) solving \(D\), so that the running time \(t_ A(x)\) of \(A\) is polynomial on the average with respect to the distribution \(\mu\). This last condition means that \[ \sum_{x\in\{0,1\}:*}t_ A(x):\epsilon \cdot \mu(x)-\mu(x')/x<\infty \] for some constant \(\varepsilon > 0\), where \(x'\) is the immediate predecessor of the string \(x\). It is not clear whether \(DistNP\subseteq Average-P\) (even if \(P\neq NP\)). The authors show that this question is related to a classical one in worst case complexity: it is proved that \(DistNP\subseteq Average-P\) implies \(NTime(2:0(n))=DTime(2:0(n))\). It is also proved that if \(DistNP\) is not contained in Average-\(P\) then there exists a problem in \(DistNP\) which is neither complete for \(DistNP\) nor easy on the average. In fact, it is shown that classical results about the richness of the structure of \(NP\) (under polynomial reductions) can be translated to the distributional context (under ``average polynomial'' reductions).