Generic-case complexity

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.

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. The ball of radius n is B_n=\{x\in I \mid \sigma(x)\le n \} . If the inputs are coded as strings over a finite alphabet, size might be the string length. Let \{\mu_n\} be an ensemble of probability distributions where \mu_n is a probability distribution on B_n . If the balls B_n are finite, then each \mu_n can be taken to be the equiprobable distribution which is the most common case. Notice that only finitely many B_n 's can be empty or have \mu_n(B_n) = 0 ; we ignore them. Definition 2. The asymptotic density of a subset X \subset I is \rho(X) = \lim_{n \to \infty}\mu_n(X \cap B_n) when this limit exists. When the balls B_n are finite and \mu_n is the equiprobable measure, \rho(X)=\lim \frac . In this case it is often convenient to use spheres I_n=\{x\in I\mid \sigma(x)=n\} instead of balls and define \rho'(X)=\lim \frac . An argument using Stolz theorem shows that \rho(X) exists if \rho'(X) does, and in that case they are equal. Definition 3 X\subseteq I is generic if \rho(X)=1 and negligible if \rho(X)=0 . 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 \mu_n(X\cap B_n) converges to 1. Superpolynomial convergence seems to be fast enough. within p(n) steps on all but p(n) inputs of size n. Clearly, APT algorithms are included in our class GenP. We have seen several NP complete problems in GenP, but Meyer and Paterson show that this is not the case for APT. They prove that an NP complete problem is reducible to a problem in APT if and only if P = NP. Thus APT seems much more restrictive than GenP. Suppose that T(w)=n for all but one word in each I_n , and T(w)=2^{2^n} on the exceptional words. In this example T is certainly polynomial on typical inputs, but T is not polynomial on average. T is in GenP. Example 2 Keep I and \sigma(w) = |w| as before, but define \mu(w)= 2^{-2|w|-1} and T(w) = 2^ . T is polynomial on average even though it is exponential on typical inputs. T is not in GenP. In these two examples the generic complexity is more closely related to behavior on typical inputs than average case complexity. Average case complexity measures something else: the balance between the frequency of difficult instances and the degree of difficulty. Roughly speaking an algorithm which is polynomial time on average can have only a subpolynomial fraction of inputs that require superpolynomial time to compute. Nevertheless, in some cases generic and average case complexity are quite close to each other. A function f:I\rightarrow\mathbb{R}^+ is polynomial on \mu -average on spheres if there exists k \geq 1 such that \sum_{w\in I_n} f^{1/k}(w) \mu_n(w) = O(n) where \{\mu_n\} is the ensemble induced by \mu . If f is polynomial on \mu -average on spheres, the f is polynomial on \mu -average, and for many distributions the converse holds Theorem 5 If a function f:I\rightarrow \mathbb{R}^+ is polynomial on \mu -average on spheres then f is generically polynomial relative to the spherical asymptotic density \rho' . Theorem 6 Suppose a complete algorithm \mathcal{A} has subexponential time bound T and a partial algorithm \mathcal{B} for the same problem is in ExpGenP with respect to the ensemble \{\mu_n\} corresponding to a probability measure \mu on the inputs I for \mathcal{A} . Then there is a complete algorithm which is \mu -average time complexity.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1368935169 under CC BY-SA 4.0; modifications have been made.