View source for Average-case computational complexity

The efficiency of an algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a1303101.png" /> is measured by the amount of computational resources used, in the first place time (number of computation steps) and space (amount of memory cells). These values may depend on the individual inputs given to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a1303102.png" />. Thus, in general it is infeasible to give a complete description of the efficiency of an algorithm, simply because the amount of data grows exponentially with respect to the size of the inputs.

Traditionally, one has considered the so-called worst-case complexity, which for each input size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a1303103.png" /> determines the maximum amount of resources used by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a1303104.png" /> on any input of that size. This conservative estimation provides a guaranteed upper bound, but in specific cases may be much too pessimistic. The simplex algorithm is a well-known example that is heavily used in practice since it tends to find a solution very fast [[#References|[a3]]]. In the worst case, however, it requires an exponential amount of time [[#References|[a12]]].

To estimate the average-case behaviour of an algorithm precisely is quite a difficult task in general. Only few examples are known where this has been achieved so far (as of 2000; compare [[#References|[a6]]]). Quick-sort is one of the most extensively investigated algorithms. To sort <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a1303105.png" /> data items, it shows a quadratic worst-case and a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a1303106.png" /> average-case time complexity [[#References|[a22]]]. For a more detailed analysis of its running time beyond the expectation, see [[#References|[a21]]]. These results have been shown for the uniform distribution, where every permutation of the input data is equally likely. For biased distributions, the analysis becomes significantly more complicated, and for arbitrary distributions the claim is no longer true. The average-case behaviour of standard quick-sort decreases significantly if the input sequence tends to be partially presorted. See below for more details on the influence of the distribution.

To determine the average-case complexity of an algorithmic problem <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a1303107.png" />, i.e. to find the  "best"  algorithm for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a1303108.png" /> with respect to the average utilization of its resources, is even harder. The sorting problem is one of the rare positive exceptions, since a matching lower bound can be derived by an information-theoretic argument almost as simple as for the worst case. Again, the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a1303109.png" /> lower bound only holds for the uniform distribution; for arbitrary distributions it has to be replaced by their entropy.

For most problems that are believed not to be efficiently solvable in the worst case, for example the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031011.png" />-complete ones (cf. also [[Computational complexity classes|Computational complexity classes]]; [[Complexity theory|Complexity theory]]; [[NP|<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031012.png" />]]), little is known about their average-case complexity. For example, for SAT, the satisfiability problem for Boolean formulas in [[conjunctive normal form]], quite a large variation of behaviour has been observed for different satisfiability algorithms (for an overview, see [[#References|[a19]]]). For certain distributions they perform quite well, but the question arises what are  "reasonable"  or  "typical"  distributions. Similar behaviour occurs for combinatorial optimization problems based on graphs if the distribution is given according to the random graph model [[#References|[a5]]]. For example, if the edge probability is not extremely small, the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031013.png" />-complete problems  "3-colourability"  and  "Hamiltonian circuit"  can easily be solved, simply because almost-all such random graphs contain a Hamiltonian circuit and also a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031015.png" />-clique, thus cannot be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031016.png" />-coloured [[#References|[a2]]], [[#References|[a7]]].

For SAT the relation between the number of clauses and the number of variables seems to be most important: with few clauses a random formula has a lot of satisfying assignments which can be found quickly. On the other hand, many clauses are likely to make a random formula unsatisfiable and there is a good chance that a proof for this property can be deduced fast. For SAT there is no simple notion of a uniform distribution, but there exists a critical relation between the number of clauses and variables, for which a random formula fulfilling this relation is equally likely to be satisfiable or unsatisfiable. It has been conjectured that this boundary behaves like a phase transition with a numerical value around <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031017.png" />, like it is known for properties of random graphs [[#References|[a17]]], [[#References|[a13]]]. For distributions in this range the average-case complexity of SAT is still unresolved (as of 2000; see also [[#References|[a14]]]).

Complexity estimations have to be based on a precise machine model. For static models like straight-line programs, all inputs of a given size are treated by the same sequence of operations, thus there is no difference in the running time. Boolean circuits seem to behave similarly if one measures the length of the computation simply by the circuit depth. However, a dynamic notion of delay has been established such that for different inputs the results of the computation are available at different times [[#References|[a9]]]. Thus, the average-case behaviour is not identical to the worst-case behaviour — an average-case analysis makes sense. A precise complexity estimation has been given for many Boolean functions, exhibiting in some cases a provable exponential speed-up of the average-case complexity in comparison to the worst-case complexity [[#References|[a11]]]. This holds for a wide range of distributions. The complexity for generating the distributions has a direct influence on the average-case behaviour of circuits.

If one bases the complexity analysis on machine models like the [[Turing machine|Turing machine]] or the random access machine (RAM), the situation gets even more complicated. In contrast to the circuit model, where for each circuit the number of input bits it can handle is fixed — thus a family of circuits is needed for different input sizes —, now a single machine can treat inputs of arbitrary length. Hence, there are two kinds of degree to which one can average the behaviour of an algorithm. First, for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031018.png" /> one could measure the expected runtime given a probability distribution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031019.png" /> on the set of all inputs of size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031020.png" />. Thus, for each input size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031021.png" />, a corresponding distribution is required. One then requires that this expectation as a function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031022.png" /> is majorized by a desired complexity bound, like a linear or polynomial function. A more general approach would be to have a single probability distribution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031023.png" /> defined over the whole input space. Then one could also weight different input sizes — not all values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031024.png" /> have to be equally important.

It has been observed that there exists a universal distribution that makes the average-case complexity of any algorithm as bad as its worst-case complexity up to a constant factor [[#References|[a15]]]. Such distributions are called malign. Fortunately, the universal distribution is not computable, i.e. there does not exist a mechanical procedure to generate input instances according to this distribution. Thus, this universally bad distribution will probably not occur  "in real life" . From these results one can infer that an average-case analysis has to take the underlying distribution carefully into account and that a significantly better average-case behaviour can only be expected for computationally simple distributions. A simple notion for this purpose is polynomial-time computability [[#References|[a16]]]. It requires that given a (natural) linear ordering <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031025.png" /> on the problem instances, the aggregated probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031026.png" /> of a distribution with density function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031027.png" /> (cf. also [[Density of a probability distribution|Density of a probability distribution]]) can be computed in polynomial time (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031028.png" />). Finer differentiations are discussed in [[#References|[a1]]], [[#References|[a18]]], [[#References|[a20]]], [[#References|[a10]]]. From a global distribution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031029.png" /> one can derive its normalized restriction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031030.png" /> to inputs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031031.png" /> of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031032.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031033.png" />.

For most algorithmic problems, already the worst-case complexity has not yet been determined precisely. But a lot of relative classifications are known, comparing the complexity of one problem to that of another problem. This is obtained by reductions between problems. Useful here are many-one reductions, i.e. mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031034.png" /> from instances <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031035.png" /> for a problem <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031036.png" /> to instances <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031037.png" /> of a problem <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031038.png" />, such that from the instance <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031039.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031040.png" /> and its solution with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031041.png" /> one can easily deduce a solution for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031042.png" /> with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031043.png" />. In the case of decision problems, for example, where for every instance the answer is either  "yes"  or  "no" , one simply requires that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031044.png" /> has the same answer as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031045.png" />. Thus, an algorithm solving <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031046.png" /> together with a reduction from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031047.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031048.png" /> can be used to solve <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031049.png" />. In order to make this transformation meaningful, the reduction itself should be of lower complexity than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031050.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031051.png" />. Then one can infer that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031052.png" /> is at most as difficult as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031053.png" />. Polynomial-time many-one reductions require that the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031054.png" /> can be computed in polynomial time. They play a central role in complexity analysis, since the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031056.png" />, polynomial time complexity, is a very robust notion to distinguish algorithmic problems that are feasibly solvable from the intractable ones. To investigate the complexity classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031057.png" /> above <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031058.png" />, a problem <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031059.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031060.png" /> with the property that all problems in this class can be reduced to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031061.png" /> is called complete for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031062.png" />. Such a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031063.png" /> can be considered as a hardest problem in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031064.png" /> — an efficient solution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031065.png" /> would yield efficient solutions for all other problems in this class. Complete problems capture the intrinsic complexity of a class.

This methodology has been established well for worst-case complexity. When trying to apply it to the average case, one faces several technical difficulties. Now one has to deal with pairs, consisting of a problem <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031066.png" /> and a distribution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031067.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031068.png" />, called distributional problems. A meaningful reduction between such problems <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031069.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031070.png" /> has to make sure that likely instances of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031071.png" /> are mapped to likely instances of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031072.png" />, a property called dominance [[#References|[a16]]]. Secondly, polynomial on average time complexity cannot simply be defined by taking the expectation, which would mean that for an algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031073.png" /> with individual running times <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031074.png" /> on inputs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031075.png" /> the inequality

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031076.png" /></td> </tr></table>

has to hold for some fixed exponent <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031077.png" /> (where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031078.png" /> denotes the normalized restriction of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031079.png" /> as defined above). This would destroy the closure properties of polynomial time reductions. Instead, the relation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031080.png" /></td> </tr></table>

is demanded for some number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031081.png" />, which is more robust against polynomial increase of running times and takes better into account the global probability distribution over the input space [[#References|[a16]]].

To establish a notion corresponding to the worst-case class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031082.png" />, one can consider distributional problems <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031083.png" /> and require that there exists an algorithm solving <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031084.png" /> in time polynomial on average with respect to this specific <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031085.png" /> — this class is named <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031086.png" />, average-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031090.png" />.

Alternatively, to allow a direct comparison to worst-case classes, one can restrict to computational problems <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031091.png" /> and require that they can be solved polynomially on average for all distributions up to a certain complexity, for example for all polynomial-time computable distributions.

The hope that important worst-case intractable problems could be solved efficiently on average for polynomial-time computable distributions, in the case of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031092.png" /> called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031094.png" />, is questionable. There exists a surprisingly simple relation to worst-case complexity, namely the deterministic and non-deterministic exponential-time classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031096.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a13031098.png" />. If they are different — which is generally believed to be true, but a weaker condition than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310100.png" /> —, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310101.png" /> is not contained in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310102.png" />; in other words, there exist <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310103.png" />-complete problems such that their distributional counterparts cannot be solved by a deterministic algorithm efficiently on the average.

An example of such a problem complete for the average case is the following so-called domino tiling problem [[#References|[a16]]]. Given a set of dominos and a square partially covered with some of them, it requires one to fill the square completely. Every domino on each of its four sides carries a mark and in a legal tiling adjacent dominos must have identical marks at neighbouring sides. However, the number of problems complete for the average case that are known so far is significantly smaller than that for the worst case [[#References|[a8]]].

To obtain a measure for average-case complexity that allows a better separation than simply polynomial or super-polynomial, these approaches have to be refined significantly. Given a time bound <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310104.png" />, the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310106.png" /> contains all distributional problems <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310107.png" /> solvable by an algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310108.png" /> such that its average-case behaviour obeys the following bound for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310109.png" />:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310110.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310111.png" /> denotes a suitably defined inverse function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310112.png" />. Given also a complexity bound <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310113.png" /> on the distributions, the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310115.png" /> consists of all problems <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310116.png" /> that for all distributions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310117.png" /> of complexity at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310118.png" /> can be solved in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310119.png" />-average time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310120.png" />. This way, hierarchy results have been obtained for the average-case complexity similar to the worst case, showing that any slight increase of computation time or any slight decrease of the distribution complexity allows one to solve more algorithmic problems [[#References|[a20]]], [[#References|[a4]]]. By diagonalization arguments one can even exhibit problems with worst-case time complexity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310121.png" /> that cannot be solved in average time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310122.png" /> for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130310/a130310123.png" />.

For a detailed discussion of these concepts and further results, see [[#References|[a8]]], [[#References|[a1]]], [[#References|[a23]]], [[#References|[a20]]], [[#References|[a24]]], [[#References|[a25]]].

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  S. Ben-David,   B. Chor,   O. Goldreich,   M. Luby,   "On the theory of average case complexity"  ''J. Comput. Syst. Sci.'' , '''44'''  (1992)  pp. 193–219</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  E. Bender,   H. Wilf,   "A theoretical analysis of backtracking in the graph coloring problem"  ''J. Algorithms'' , '''6'''  (1985)  pp. 275–282</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  K. Borgwardt,   "The average number of pivot steps required by the simplex-method is polynomial"  ''Z. Operat. Res.'' , '''26'''  (1982)  pp. 157–177</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  J. Cai,   A. Selman,   "Fine separation of average time complexity classes" , ''Proc. 13 Symp. Theoret. Aspects of Computer Sci.'' , ''Lecture Notes in Compter Sci.'' , '''1046''' , Springer  (1996)  pp. 331–343</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  P. Erdös,   A. Renyi,   "On the strength of connectedness of a random graph"  ''Acta Math. Acad. Sci. Hungar.'' , '''12'''  (1961)  pp. 261–267</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  P. Flajolet,   B. Salvy,   P. Zimmermann,   "Automatic average-case analysis of algorithms"  ''Theoret. Computer Sci.'' , '''79'''  (1991)  pp. 37–109</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  Y. Gurevich,   S. Shelah,   "Expected computation time for Hamiltonian path problem"  ''SIAM J. Comput.'' , '''16'''  (1987)  pp. 486–502</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  Y. Gurevich,   "Average case completeness"  ''J. Comput. Syst. Sci.'' , '''42'''  (1991)  pp. 346–398</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  A. Jakoby,   R. Reischuk,   C. Schindelhauer,   "Circuit complexity: From the worst case to the average case" , ''Proc. 25th ACM Symp. Theory of Computing''  (1994)  pp. 58–67</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  A. Jakoby,   R. Reischuk,   C. Schindelhauer,   "Malign distributions for average case circuit complexity"  ''Inform. &amp; Comput.'' , '''150'''  (1999)  pp. 187–208</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  A. Jakoby,   "Die Komplexität von Präfixfunktionen bezüglich ihres mittleren Zeitverhaltens"  ''Diss. Univ. Lübeck, Shaker''  (1997)</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  V. Klee,   G. Minty,   "How good is the simplex algorithm" , ''Inequalities'' , '''III''' , Acad. Press  (1972)  pp. 159–175</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  A. Kamath,   R. Motwani,   K. Palem,   P. Spirakis,   "Tail bounds for occupancy and the satisfiability threshold"  ''Random Struct. Algor.'' , '''7'''  (1995)  pp. 59–80</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  J. Kratochvil,   P. Savicky,   Z. Tuza,   "One more occurence of variables makes satisfiability jump from trivial to NP-complete"  ''SIAM J. Comput.'' , '''22'''  (1993)  pp. 203–210</TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top">  M. Li,   P. Vitanyi,   "Average case complexity under the universal distribution equals worst case complexity"  ''Inform. Proc. Lett.'' , '''42'''  (1992)  pp. 145–149</TD></TR><TR><TD valign="top">[a16]</TD> <TD valign="top">  L. Levin,   "Average case complete problems"  ''SIAM J. Comput.'' , '''15'''  (1986)  pp. 285–286</TD></TR><TR><TD valign="top">[a17]</TD> <TD valign="top">  D. Mitchel,   B. Selman,   H. Levesque,   "Hard and easy distributions of SAT problems" , ''Proc. 10th Amer. Assoc. Artificial Intelligence'' , AAAI/MIT  (1992)  pp. 459–465</TD></TR><TR><TD valign="top">[a18]</TD> <TD valign="top">  P. Miltersen,   "The complexity of malign measures"  ''SIAM J. Comput.'' , '''22'''  (1993)  pp. 147–156</TD></TR><TR><TD valign="top">[a19]</TD> <TD valign="top">  P. Purdom,   "A survey of average time analysis of satisfiability algorithms"  ''J. Inform. Proces.'' , '''13'''  (1990)  pp. 449–455</TD></TR><TR><TD valign="top">[a20]</TD> <TD valign="top">  R. Reischuk,   C. Schindelhauer,   "An average complexity measure that yields tight hierarchies"  ''Comput. Complexity'' , '''6'''  (1996)  pp. 133–173</TD></TR><TR><TD valign="top">[a21]</TD> <TD valign="top">  U. Rösler,   "A limit theorem for quicksort"  ''Theoret. Inform. Appl.'' , '''25'''  (1991)  pp. 85–100</TD></TR><TR><TD valign="top">[a22]</TD> <TD valign="top">  R. Sedgewick,   "The analysis of quicksort programs"  ''Acta Inform.'' , '''7'''  (1977)  pp. 327–355</TD></TR><TR><TD valign="top">[a23]</TD> <TD valign="top">  J. Wang,   J. Belanger,   "On average P vs. average NP"  K. Ambos-Spies (ed.)  S. Homer (ed.)  U. Schning (ed.) , ''Complexity Theory Current Research'' , Cambridge Univ. Press  (1993)  pp. 47–68</TD></TR><TR><TD valign="top">[a24]</TD> <TD valign="top">  J. Wang,   "Average-case computational complexity theory"  A. Selman (ed.)  L. Hemaspaandra (ed.) , ''Complexity Theory Retrospective'' , '''II''' , Springer  (1997)  pp. 295–328</TD></TR><TR><TD valign="top">[a25]</TD> <TD valign="top">  J. Wang,   "Average-case intractable problems"  D. Du (ed.)  K. Ko (ed.) , ''Advances in Languages, Algorithms, and Complexity'' , Kluwer Acad. Publ.  (1997)  pp. 313–378</TD></TR></table>