Generic-case complexity is a subfield of computational complexity theory that studies the complexity of computational problems on "most inputs".
Generic-case complexity is a way of measuring the complexity of a computational problem by neglecting a small set of unrepresentative inputs and considering worst-case complexity on the rest. Small is defined in terms of asymptotic density. The apparent efficacy of generic case complexity is because for a wide variety of concrete computational problems, the most difficult instances seem to be rare. Typical instances are relatively easy.
This approach to complexity originated in combinatorial group theory, which has a computational tradition going back to the beginning of the last century. The notion of generic complexity was introduced in a 2003 paper, where authors showed that for a large class of finitely generated groups the generic time complexity of some classical decision problems from combinatorial group theory, namely the word problem, conjugacy problem and membership problem, are linear.
A detailed introduction of generic case complexity can be found in the surveys.
Basic definitions
Asymptotic density
Let I be an infinite set of inputs for a computational problem.
Definition 1. A size function on I is a map with infinite range. The ball of radius n is .
If the inputs are coded as strings over a finite alphabet, size might be the string length.
Let be an ensemble of probability distributions where is a probability distribution on . If the balls are finite, then each can be taken to be the equiprobable distribution which is the most common case. Notice that only finitely many 's can be empty or have ; we ignore them.
Definition 2. The asymptotic density of a subset is when this limit exists.
When the balls are finite and is the equiprobable measure,
In this case it is often convenient to use spheres instead of balls and define . An argument using Stolz theorem shows that exists if does, and in that case they are equal.
Definition 3 is generic if and negligible if . X is exponentially (superpolynomially) generic if the convergence to the limit in Definition 2 is exponentially (superpolynomially) fast, etc.
A generic subset X is asymptotically large. Whether X appears large in practice depends on how fast converges to 1. Superpolynomial convergence seems to be fast enough.
Generic complexity classes
Definition 4 An algorithm is in GenP (generically polynomial time) if it never gives incorrect answers and if it gives correct answers in polynomial time on a generic set of inputs. A problem is in GenP if it admits an algorithm in GenP. Likewise for GenL (generically linear time), GenE (generically exponential time with a linear exponent) GenExp (generically exponential time), etc. ExpGenP is the subclass of GenP for which the relevant generic set is exponentially generic.
More generally for any we can define the class Gen(f) corresponding to
time complexity O(f) on a generic set of input.
Definition 5. An algorithm solves a problem generically if it never gives incorrect answers and if it gives correct answers on a generic set of inputs. A problem is generically solvable if it is solved generically by some algorithm.
Theory and applications
Combinatorial group theory problems
The famous undecidable problems: under suitable hypotheses, the word, conjugacy and membership decision problems are in generically polynomial. The word and conjugacy search problems are in GenP for all fixed finitely presented groups.
The well known coset enumeration procedure admits a computable upper bound on a generic set of inputs.
The Whitehead algorithm for testing whether or not one element of a free group is mapped to another by an automorphism has an exponential worst case upper bound but runs well in practice. The algorithm is shown to be in GenL.
The conjugacy problem in HNN extensions can be unsolvable even for free groups. However, it is generically cubic time.
The halting problem and the Post correspondence problem
The halting problem for Turing machine with one-sided tape is easily decidable most of the time; it is in GenP
The situation for two-sided tape is unknown. However, there is a kind of lower bound for machines of both types. The halting problem is not in ExpGenP for any model of Turing machine,
The Post correspondence problem is in ExpGenP.