On the theory of average case complexity
type: Item
instance of: scholarly article
title: On the theory of average case complexity
zbMATH Open document ID: 0762.68027
DOI: 10.1016/0022-0000(92)90019-F
author: Shai Ben-David
author: Benny Chor
author: Oded Goldreich
author: Michel Luby
published in: Journal of Computer and System Sciences
publication date: 1992-09-27T00:00:00Z
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).
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 58806
zbMATH Keywords: average case complexity
zbMATH Keywords: distributional decision problem
reviewed by: Stasys Jukna
MaRDI profile type: Publication
cites work: Universal classes of hash functions
cites work: Q4138187
cites work: Q4198056
cites work: Time polynomial in input or output
cites work: Q3972530
cites work: The NP-completeness column: An ongoing guide
cites work: Q4142699
cites work: Q4173215
cites work: On the Structure of Polynomial Time Reducibility
cites work: Q4071737
cites work: Average Case Complete Problems
cites work: One way functions and pseudorandom generators
cites work: On uniform circuit complexity
cites work: NP is as easy as detecting unique solutions
full work available at URL: 0022-0000(92)90019-f
OpenAlex ID: W2173249896
description: scientific article; zbMATH DE number 58806