On the theory of average case complexity

DOI10.1016/0022-0000(92)90019-FMaRDI QIDQ1190984zbMATH OpenOpenAlexFDO

Authors Shai Ben-David, Benny Chor, Oded Goldreich, Michel Luby

Publication date 27 September 1992

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(92)90019-f

average case complexity distributional decision problem

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Review text

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).

Cited in

(69)

This page was built for publication: On the theory of average case complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1190984)