Average-case complexity

Last updated April 22, 2023

In computational complexity theory, the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs. It is frequently contrasted with worst-case complexity which considers the maximal complexity of the algorithm over all possible inputs.

There are three primary motivations for studying average-case complexity.^[1] First, although some problems may be intractable in the worst-case, the inputs which elicit this behavior may rarely occur in practice, so the average-case complexity may be a more accurate measure of an algorithm's performance. Second, average-case complexity analysis provides tools and techniques to generate hard instances of problems which can be utilized in areas such as cryptography and derandomization. Third, average-case complexity allows discriminating the most efficient algorithm in practice among algorithms of equivalent best case complexity (for instance Quicksort).

Average-case analysis requires a notion of an "average" input to an algorithm, which leads to the problem of devising a probability distribution over inputs. Alternatively, a randomized algorithm can be used. The analysis of such algorithms leads to the related notion of an expected complexity.^[2]^: 28

History and background

The average-case performance of algorithms has been studied since modern notions of computational efficiency were developed in the 1950s. Much of this initial work focused on problems for which worst-case polynomial time algorithms were already known.^[3] In 1973, Donald Knuth ^[4] published Volume 3 of the Art of Computer Programming which extensively surveys average-case performance of algorithms for problems solvable in worst-case polynomial time, such as sorting and median-finding.

An efficient algorithm for $NP$ -complete problems is generally characterized as one which runs in polynomial time for all inputs; this is equivalent to requiring efficient worst-case complexity. However, an algorithm which is inefficient on a "small" number of inputs may still be efficient for "most" inputs that occur in practice. Thus, it is desirable to study the properties of these algorithms where the average-case complexity may differ from the worst-case complexity and find methods to relate the two.

The fundamental notions of average-case complexity were developed by Leonid Levin in 1986 when he published a one-page paper^[5] defining average-case complexity and completeness while giving an example of a complete problem for $distNP$ , the average-case analogue of $NP$ .

Definitions

Efficient average-case complexity

The first task is to precisely define what is meant by an algorithm which is efficient "on average". An initial attempt might define an efficient average-case algorithm as one which runs in expected polynomial time over all possible inputs. Such a definition has various shortcomings; in particular, it is not robust to changes in the computational model. For example, suppose algorithm $A$ runs in time $t A (x)$ on input $x$ and algorithm $B$ runs in time $t A (x) 2$ on input $x$ ; that is, $B$ is quadratically slower than $A$ . Intuitively, any definition of average-case efficiency should capture the idea that $A$ is efficient-on-average if and only if $B$ is efficient on-average. Suppose, however, that the inputs are drawn randomly from the uniform distribution of strings with length $n$ , and that $A$ runs in time $n 2$ on all inputs except the string $1 n$ for which $A$ takes time $2 n$ . Then it can be easily checked that the expected running time of $A$ is polynomial but the expected running time of $B$ is exponential.^[3]

To create a more robust definition of average-case efficiency, it makes sense to allow an algorithm $A$ to run longer than polynomial time on some inputs but the fraction of inputs on which $A$ requires larger and larger running time becomes smaller and smaller. This intuition is captured in the following formula for average polynomial running time, which balances the polynomial trade-off between running time and fraction of inputs:

\Pr _{x\in _{R}D_{n}}\left[t_{A}(x)\geq t\right]\leq {\frac {p(n)}{t^{\epsilon }}}

for every $n, t > 0$ and polynomial $p$ , where $t A (x)$ denotes the running time of algorithm $A$ on input $x$ , and $ε$ is a positive constant value.^[6] Alternatively, this can be written as

E_{x\in _{R}D_{n}}\left[{\frac {t_{A}(x)^{\epsilon }}{n}}\right]\leq C

for some constants $C$ and $ε$ , where $n = | x |$ .^[7] In other words, an algorithm $A$ has good average-case complexity if, after running for $t A (n)$ steps, $A$ can solve all but a $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}nc/(tA(n))ε$ fraction of inputs of length $n$ , for some $ε, c > 0$ .^[3]

Distributional problem

The next step is to define the "average" input to a particular problem. This is achieved by associating the inputs of each problem with a particular probability distribution. That is, an "average-case" problem consists of a language $L$ and an associated probability distribution $D$ which forms the pair $(L, D)$ .^[7] The two most common classes of distributions which are allowed are:

Polynomial-time computable distributions ( $P$ -computable): these are distributions for which it is possible to compute the cumulative density of any given input $x$ . More formally, given a probability distribution $μ$ and a string $x \in {0, 1} n$ it is possible to compute the value $\mu (x)=\sum \limits _{y\in \{0,1\}^{n}:y\leq x}\Pr[y]$ in polynomial time. This implies that $Pr[x]$ is also computable in polynomial time.
Polynomial-time samplable distributions ( $P$ -samplable): these are distributions from which it is possible to draw random samples in polynomial time.

These two formulations, while similar, are not equivalent. If a distribution is $P$ -computable it is also $P$ -samplable, but the converse is not true if $P$ ≠ $P #P$ .^[7]

AvgP and distNP

A distributional problem $(L, D)$ is in the complexity class $AvgP$ if there is an efficient average-case algorithm for $L$ , as defined above. The class $AvgP$ is occasionally called $distP$ in the literature.^[7]

A distributional problem $(L, D)$ is in the complexity class $distNP$ if $L$ is in $NP$ and $D$ is $P$ -computable. When $L$ is in $NP$ and $D$ is $P$ -samplable, $(L, D)$ belongs to $sampNP$ .^[7]

Together, $AvgP$ and $distNP$ define the average-case analogues of $P$ and $NP$ , respectively.^[7]

Reductions between distributional problems

Let $(L, D)$ and $(L', D')$ be two distributional problems. $(L, D)$ average-case reduces to $(L', D')$ (written $(L, D) \leq AvgP (L', D')$ ) if there is a function $f$ that for every $n$ , on input $x$ can be computed in time polynomial in $n$ and

(Correctness) $x \in L$ if and only if $f (x) \in L'$
(Domination) There are polynomials $p$ and $m$ such that, for every $n$ and $y$ , $\sum \limits _{x:f(x)=y}D_{n}(x)\leq p(n)D'_{m(n)}(y)$

The domination condition enforces the notion that if problem $(L, D)$ is hard on average, then $(L', D')$ is also hard on average. Intuitively, a reduction should provide a way to solve an instance $x$ of problem $L$ by computing $f (x)$ and feeding the output to the algorithm which solves $L'$ . Without the domination condition, this may not be possible since the algorithm which solves $L$ in polynomial time on average may take super-polynomial time on a small number of inputs but $f$ may map these inputs into a much larger set of $D'$ so that algorithm $A'$ no longer runs in polynomial time on average. The domination condition only allows such strings to occur polynomially as often in $D'$ .^[6]

DistNP-complete problems

The average-case analogue to $NP$ -completeness is $distNP$ -completeness. A distributional problem $(L', D')$ is $distNP$ -complete if $(L', D')$ is in $distNP$ and for every $(L, D)$ in $distNP$ , $(L, D)$ is average-case reducible to $(L', D')$ .^[7]

An example of a $distNP$ -complete problem is the Bounded Halting Problem, $BH$ , defined as follows:

$BH=\{(M,x,1^{t}):M{\text{ is a non-deterministic Turing machine that accepts }}x{\text{ in}}\leq t{\text{ steps}}\}$ ^[7]

In his original paper, Levin showed an example of a distributional tiling problem that is average-case $NP$ -complete.^[5] A survey of known $distNP$ -complete problems is available online.^[6]

One area of active research involves finding new $distNP$ -complete problems. However, finding such problems can be complicated due to a result of Gurevich which shows that any distributional problem with a flat distribution cannot be $distNP$ -complete unless $EXP$ = $NEXP$ .^[8] (A flat distribution $μ$ is one for which there exists an $ε > 0$ such that for any $x$ , $μ (x) \leq 2 - | x | ε$ .) A result by Livne shows that all natural $NP$ -complete problems have $DistNP$ -complete versions.^[9] However, the goal of finding a natural distributional problem that is $DistNP$ -complete has not yet been achieved.^[10]

Applications

Sorting algorithms

As mentioned above, much early work relating to average-case complexity focused on problems for which polynomial-time algorithms already existed, such as sorting. For example, many sorting algorithms which utilize randomness, such as Quicksort, have a worst-case running time of $O(n 2)$ , but an average-case running time of $O(n log(n))$ , where $n$ is the length of the input to be sorted.^[2]

Cryptography

For most problems, average-case complexity analysis is undertaken to find efficient algorithms for a problem that is considered difficult in the worst-case. In cryptographic applications, however, the opposite is true: the worst-case complexity is irrelevant; we instead want a guarantee that the average-case complexity of every algorithm which "breaks" the cryptographic scheme is inefficient.^[11]

Thus, all secure cryptographic schemes rely on the existence of one-way functions.^[3] Although the existence of one-way functions is still an open problem, many candidate one-way functions are based on hard problems such as integer factorization or computing the discrete log. Note that it is not desirable for the candidate function to be $NP$ -complete since this would only guarantee that there is likely no efficient algorithm for solving the problem in the worst case; what we actually want is a guarantee that no efficient algorithm can solve the problem over random inputs (i.e. the average case). In fact, both the integer factorization and discrete log problems are in $NP \cap$ $coNP$ , and are therefore not believed to be $NP$ -complete.^[7] The fact that all of cryptography is predicated on the existence of average-case intractable problems in $NP$ is one of the primary motivations for studying average-case complexity.

Other results

In 1990, Impagliazzo and Levin showed that if there is an efficient average-case algorithm for a $distNP$ -complete problem under the uniform distribution, then there is an average-case algorithm for every problem in $NP$ under any polynomial-time samplable distribution.^[12] Applying this theory to natural distributional problems remains an outstanding open question.^[3]

In 1992, Ben-David et al. showed that if all languages in $distNP$ have good-on-average decision algorithms, they also have good-on-average search algorithms. Further, they show that this conclusion holds under a weaker assumption: if every language in $NP$ is easy on average for decision algorithms with respect to the uniform distribution, then it is also easy on average for search algorithms with respect to the uniform distribution.^[13] Thus, cryptographic one-way functions can exist only if there are $distNP$ problems over the uniform distribution that are hard on average for decision algorithms.

In 1993, Feigenbaum and Fortnow showed that it is not possible to prove, under non-adaptive random reductions, that the existence of a good-on-average algorithm for a $distNP$ -complete problem under the uniform distribution implies the existence of worst-case efficient algorithms for all problems in $NP$ .^[14] In 2003, Bogdanov and Trevisan generalized this result to arbitrary non-adaptive reductions.^[15] These results show that it is unlikely that any association can be made between average-case complexity and worst-case complexity via reductions.^[3]

Related Research Articles

In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances. BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine.

The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem.

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whether a given natural number is prime. Another is the problem "given two numbers x and y, does x evenly divide y?". The answer is either 'yes' or 'no' depending upon the values of x and y. A method for solving a decision problem, given in the form of an algorithm, is called a decision procedure for that problem. A decision procedure for the decision problem "given two numbers x and y, does x evenly divide y?" would give the steps for determining whether x evenly divides y. One such algorithm is long division. If the remainder is zero the answer is 'yes', otherwise it is 'no'. A decision problem which can be solved by an algorithm is called decidable.

In number theory, integer factorization is the decomposition, when possible, of a positive integer into a product of smaller integers. If the factors are further restricted to be prime numbers, the process is called prime factorization, and includes the test whether the given integer is prime.

In computational complexity theory, the complexity class #P (pronounced "sharp P" or, sometimes "number P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute f(x)", where f is the number of accepting paths of a nondeterministic Turing machine running in polynomial time. Unlike most well-known complexity classes, it is not a class of decision problems but a class of function problems. The most difficult, representative problems of this class are #P-complete.

The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset $of integers and a target-sum, and the question is to decide whether any subset of the integers sum to precisely . The problem is known to be NP-hard. Moreover, some restricted variants of it are NP-complete too, for example:$

In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems. Not being one-to-one is not considered sufficient for a function to be called one-way.

In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.

In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time. The complexity class was defined by Gill in 1977.

In computational complexity theory, a function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem. For function problems, the output is not simply 'yes' or 'no'.

In theoretical computer science and cryptography, a pseudorandom generator (PRG) for a class of statistical tests is a deterministic procedure that maps a random seed to a longer pseudorandom string such that no statistical test in the class can distinguish between the output of the generator and the uniform distribution. The random seed itself is typically a short binary string drawn from the uniform distribution.

Random self-reducibility (RSR) is the rule that a good algorithm for the average case implies a good algorithm for the worst case. RSR is the ability to solve all instances of a problem by solving a large fraction of the instances.

In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently. It is not known how to prove (unconditional) hardness for essentially any useful problem. Instead, computer scientists rely on reductions to formally relate the hardness of a new or complicated problem to a computational hardness assumption about a problem that is better-understood.

In computer science, lattice problems are a class of optimization problems related to mathematical objects called lattices. The conjectured intractability of such problems is central to the construction of secure lattice-based cryptosystems: Lattice problems are an example of NP-hard problems which have been shown to be average-case hard, providing a test case for the security of cryptographic algorithms. In addition, some lattice problems which are worst-case hard can be used as a basis for extremely secure cryptographic schemes. The use of worst-case hardness in such schemes makes them among the very few schemes that are very likely secure even against quantum computers. For applications in such cryptosystems, lattices over vector space or free modules are generally considered.

In computational complexity theory, a problem is NP-complete when:

It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no".
When the answer is "yes", this can be demonstrated through the existence of a short solution.
The correctness of each solution can be verified quickly and a brute-force search algorithm can find a solution by trying all possible solutions.
The problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified.

Generic-case complexity is a subfield of computational complexity theory that studies the complexity of computational problems on "most inputs".

References

↑ O. Goldreich and S. Vadhan, Special issue on worst-case versus average-case complexity, Comput. Complex. 16, 325–330, 2007.
1 2 Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.
1 2 3 4 5 6 A. Bogdanov and L. Trevisan, "Average-Case Complexity," Foundations and Trends in Theoretical Computer Science, Vol. 2, No 1 (2006) 1–106.
↑ D. Knuth, The Art of Computer Programming. Vol. 3, Addison-Wesley, 1973.
1 2 L. Levin, "Average case complete problems," SIAM Journal on Computing, vol. 15, no. 1, pp. 285–286, 1986.
1 2 3 J. Wang, "Average-case computational complexity theory," Complexity Theory Retrospective II, pp. 295–328, 1997.
1 2 3 4 5 6 7 8 9 S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, New York, NY, 2009.
↑ Y. Gurevich, "Complete and incomplete randomized NP problems", Proc. 28th Annual Symp. on Found. of Computer Science, IEEE (1987), pp. 111–117.
↑ N. Livne, "All Natural NP-Complete Problems Have Average-Case Complete Versions," Computational Complexity (2010) 19:477. https://doi.org/10.1007/s00037-010-0298-9
↑ O. Goldreich, "Notes on Levin's theory of average-case complexity," Technical Report TR97-058, Electronic Colloquium on Computational Complexity, 1997.
↑ J. Katz and Y. Lindell, Introduction to Modern Cryptography (Chapman and Hall/Crc Cryptography and Network Security Series), Chapman and Hall/CRC, 2007.
↑ R. Impagliazzo and L. Levin, "No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random," in Proceedings of the 31st IEEE Sympo- sium on Foundations of Computer Science, pp. 812–821, 1990.
↑ S. Ben-David, B. Chor, O. Goldreich, and M. Luby, "On the theory of average case complexity," Journal of Computer and System Sciences, vol. 44, no. 2, pp. 193–219, 1992.
↑ J. Feigenbaum and L. Fortnow, "Random-self-reducibility of complete sets," SIAM Journal on Computing, vol. 22, pp. 994–1005, 1993.
↑ A. Bogdanov and L. Trevisan, "On worst-case to average-case reductions for NP problems," in Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, pp. 308–317, 2003.