Average-case complexity

Average-case complexity is the branch of computational complexity theory that measures the resources used by an algorithm relative to a probability distribution over inputs. Whereas worst-case complexity assigns a resource bound according to the most expensive input of each length, average-case analysis incorporates both the cost of each input and the probability with which that input occurs. The resulting complexity therefore belongs to a pair consisting of a computational problem and an input distribution, rather than to the problem alone.

The subject provides formal models for distinguishing algorithms whose expensive executions occur with negligible probability from algorithms that require substantial resources on a significant fraction of inputs. It also supplies the complexity-theoretic language used to express hardness on average, which is central to the analysis of one-way functions, pseudorandomness, and several forms of randomized reduction.

Formal setting

Let (L\subseteq{0,1}^*) be a decision problem, and let

[ \mathcal D={D_n}_{n\geq 1} ]

be an ensemble of probability distributions, where (D_n) is supported on strings of length (n). The pair ((L,\mathcal D)) is called a distributional decision problem. If an algorithm (A) has running time (T_A(x)), its resource consumption at length (n) is treated as a random variable under (x\leftarrow D_n).

A direct expected-time definition requires

[ \operatorname{\mathbb E}_{x\leftarrow D_n}[T_A(x)] \leq p(n) ]

for some polynomial (p). This condition is stronger than the generalized average-polynomial condition used in much of complexity theory. Under the generalized definition, there are a constant (\varepsilon>0) and a polynomial (p) satisfying

[ \operatorname{\mathbb E}_{x\leftarrow D_n} \left[T_A(x)^\varepsilon\right] \leq p(n). ]

The fractional moment prevents a small collection of exceptionally expensive inputs from determining the entire classification, while still imposing a polynomial bound on the probability of long executions. By Markov's inequality, the condition implies

[ \Pr_{x\leftarrow D_n} \bigl[T_A(x)>t\bigr] \leq \frac{p(n)}{t^\varepsilon}. ]

Thus, average polynomial time is equivalently associated with a polynomially decreasing tail bound, subject to standard changes in constants and exponents. This formulation also behaves regularly under polynomial slowdowns and under composition with algorithms whose running times are polynomially related.

The distribution ensemble is an essential component of the model. The same language (L) can be easy under one ensemble and hard under another because the ensembles can assign their probability mass to different regions of the input space. Uniform distributions provide one natural case, but they do not represent instances generated by structured computational processes. Average-case complexity therefore distinguishes uniform input models from ensembles produced by efficient randomized samplers.

Distributional complexity classes

The class (\mathsf{AvgP}) contains distributional problems decidable in average polynomial time. Its definition depends on the adopted representation of distributions, although the principal formulations require the distributions to have an effective computational description.

A distribution is polynomial-time computable when relevant probability values or cumulative probabilities can be evaluated with polynomial resources under the chosen encoding. A polynomial-time samplable ensemble instead requires a probabilistic polynomial-time machine whose output follows the designated distribution. These requirements are related but not identical, since efficient generation does not automatically provide efficient evaluation of individual output probabilities.

The distributional analogue of NP is commonly denoted (\mathsf{DistNP}). A pair ((L,\mathcal D)) belongs to this class when (L) has polynomially verifiable witnesses and (\mathcal D) satisfies the specified efficient-distribution condition. The distribution changes the complexity of finding or deciding solutions on random instances, but it does not alter the underlying witness relation.

Average-case tractability is not implied by ordinary membership in (\mathsf P) under every machine model unless the algorithm has a pointwise polynomial bound. Conversely, a distributional problem may belong to (\mathsf{AvgP}) even when its algorithm takes superpolynomial time on a sparse set of inputs. The distinction is meaningful only when that sparse set also has sufficiently small probability under the designated ensemble.

Reductions and completeness

A reduction between distributional problems must preserve both membership and probability mass. An ordinary many-one reduction can map a rare source event into an even rarer target event, allowing a target algorithm to fail precisely on the image of the difficult source instances without violating its own average-time guarantee. Distributional reductions exclude this behavior through a domination requirement.

For a reduction (f) from ((L,\mathcal D)) to ((L',\mathcal D')), correctness requires

[ x\in L \quad\Longleftrightarrow\quad f(x)\in L'. ]

The pushforward of (D_n) under (f) must also be dominated, up to a polynomial factor, by the corresponding target distribution. In a representative formulation, there is a polynomial (q) such that the total source probability mapped to a target string (y) is at most

[ q(n)\Pr_{z\leftarrow D'_{m(n)}}[z=y], ]

where (m(n)) bounds the output length. This relation ensures that a low-probability failure set for the target algorithm pulls back to a low-probability failure set for the source algorithm.

During the 1980s, You Watanabe developed an ensemble-based formulation of domination-preserving reductions in which length changes and probability distortion were accounted for by a single polynomial bound. The formulation established that average-polynomial decidability transfers from the target distributional problem to the source distributional problem, provided that the reduction itself has polynomial pointwise complexity.

Completeness in (\mathsf{DistNP}) is defined with respect to reductions of this kind. A complete distributional problem represents the computational content of every problem in the class while retaining enough information about probability mass to preserve average-case algorithms. Standard constructions use bounded computation problems whose instances encode a nondeterministic machine, an input, and a time bound, together with a distribution designed to dominate the encodings produced by reductions.

Historical development

Leonid Levin introduced a systematic theory of average-case completeness during the 1980s by defining distributional problems, average-polynomial algorithms, and complete problems for distributional NP. His framework made the input distribution part of the formal computational object and replaced informal expectations over unspecified instances with explicit, reducible ensembles.

Earlier algorithmic analysis had already used expected running time for algorithms operating on random inputs. That tradition included probabilistic analyses of sorting, searching, and data structures, but such analyses generally fixed a particular input model and did not define complexity classes under distribution-preserving reductions. The distributional framework separated the analysis of a selected algorithm from the classification of problems according to average-case reducibility.

Later work connected distributional complexity with cryptographic hardness and with the structure of worst-case-to-average-case reductions. These developments treated average-case hardness as a quantifiable property of an explicit ensemble rather than as the absence of a known efficient algorithm.

Relation to worst-case complexity

Worst-case hardness does not by itself imply average-case hardness. A language can encode all of its difficult instances in a set receiving exponentially small probability under the selected ensemble, while remaining easy on nearly all sampled inputs. An (\mathsf{NP})-complete problem under ordinary polynomial-time reductions therefore need not be complete for (\mathsf{DistNP}) under its most familiar input distribution.

A worst-case-to-average-case reduction establishes a stronger relation. Such a reduction solves every instance of one problem by querying an algorithm that succeeds on a substantial fraction of instances drawn from a specified distribution. The reduction must tolerate errors or failures on part of the distribution while retaining enough information to reconstruct the worst-case answer.

Richard Lipton established a worst-case-to-average-case reduction for the permanent over sufficiently large finite fields. The argument represents the permanent along a random algebraic line as a low-degree polynomial and reconstructs its value through polynomial interpolation. The result concerns an algebraically structured distribution and does not directly convert arbitrary worst-case hardness into average-case hardness over unrestricted binary encodings.

Miklós Ajtai obtained a different form of worst-case-to-average-case connection for lattice problems, relating the solution of random instances to the solution of designated lattice problems in the worst case. Subsequent lattice-based constructions refined the approximation factors, distributions, and computational assumptions involved. These reductions differ from distributional completeness reductions because they transfer hardness from a worst-case problem to a particular random-instance problem rather than organizing an entire distributional complexity class.

Average-case hardness and cryptography

Cryptographic constructions require hardness on inputs produced by efficient generation procedures. Worst-case intractability alone is insufficient because an adversary interacts with keys, challenges, or public parameters sampled from designated distributions. The relevant security condition therefore concerns the probability of successful inversion or prediction over those distributions.

A one-way function is efficiently computable but resistant to inversion on the distribution obtained by applying the function to a random input. Its existence yields problems in NP whose associated distributions are hard on average under corresponding notions of success. The precise equivalence depends on whether hardness is expressed through decision, search, inversion, or relation problems, since converting among these formulations can require additional structure.

Average-case hardness also underlies pseudorandom generators, which expand a short random seed into a longer string that cannot be efficiently distinguished from the appropriate reference distribution. Here the relevant average is taken over sampled seeds and the internal randomness of the distinguisher. This use of probability concerns adversarial success rather than solely the expected running time of a deterministic solver, but both formulations rely on explicit ensembles and asymptotic probability bounds.

Comparison with related analyses

Average-case complexity differs from the expected running-time analysis of a randomized algorithm. In the latter setting, the input may remain fixed while the expectation is taken over the algorithm's internal random choices. In distributional complexity, the expectation is taken over inputs, although a randomized solver introduces an additional source of probability that can be incorporated into the same formal model.

It also differs from smoothed analysis, which begins with an arbitrary instance and then applies a controlled random perturbation. Smoothed complexity takes the worst case over the unperturbed instance while averaging over the perturbation. This arrangement prevents the analysis from depending entirely on a globally fixed input distribution, while still excluding highly unstable pathological instances from determining every bound.

Parameterized complexity organizes resource usage according to an explicit structural parameter rather than an input probability. A distribution can nevertheless be conditioned on parameter values, producing models that track both probabilistic frequency and parameter dependence. The two frameworks answer distinct questions because a rare parameter regime can remain decisive in parameterized analysis while contributing little to an unconditional average.

Interpretive limitations

An average-case bound is meaningful only relative to its stated ensemble. Empirical frequency, uniform sampling, and algorithmic generation define different distributions even when their support contains the same encoded instances. Replacing one ensemble with another can change the complexity classification without changing the language or the solving algorithm.

Expected resource bounds also summarize the tail of a distribution less completely than explicit probability estimates. Two algorithms can have the same asymptotic expectation while exhibiting different probabilities of exceeding a particular time threshold. Complexity-theoretic definitions therefore use moment conditions, domination properties, or success probabilities suited to the reduction and hardness notions under examination.

Encoding choices have a greater role than in pointwise polynomial-time complexity because an encoding affects both input length and probability mass. Distributional reductions control this dependence by bounding length expansion and probability distortion. Without those constraints, padding or probability concentration could transform an average-hard problem into an average-easy representation without altering its logical content.