Generic-case complexity, decision problems in group theory, and random walks. (Q1399190)

The authors suggest a precise definition of generic-case complexity of a decision problem in group theory and show that for a very large class of finitely generated groups the word, membership, and conjugacy problems all have linear-time generic-case complexity. The idea of generic-case complexity is that for some decision problems (which may have high worst-case complexity or even be unsolvable) there is an algorithm which quickly produces a solution for ``most'' inputs of the problem. For a set \(S\) of \(k\)-tuples of words over a finite alphabet \(X\), let \(\rho_n(S)=|S\cap B_n)|/|B_n|\), where \(B_n\) is the set of all \(k\)-tuples of words over \(X\) of total length \(\leq n\). The set \(S\) is called generic if its asymptotic density is 1, that is, \(\rho_n(S)\to 1\) as \(n\to\infty\). If, in addition, \(\rho_n(S)\to 1\) exponentially fast (which means that there exist \(C>0\) and \(0\leq r<1\) such that \(|\rho_n(S)-1|\leq Cr^n\)) then \(S\) is called strongly generic. Let \(\mathcal C\) be a complexity class (e.g. linear time, polynomial time), and \(G\) a finitely generated group. A decision problem \(D\) for \(G\) is defined to have generic-case complexity in \(\mathcal C\) (strongly in \(\mathcal C\)) if for every generating set \(A\) of \(G\) there exist a correct partial algorithm \(\Omega_A\) for the \(A\)-version of \(D\) and a generic (strongly generic) set of its inputs \(S\) such that for any \(\sigma\in S\) the algorithm \(\Omega_A\) terminates on \(\sigma\) within the complexity bound \(\mathcal C\). Here are the main results of the paper. Suppose \(G\) has a finite index subgroup \(H\) that possesses an infinite quotient group \(\overline H\) for which the word problem is solvable in \(\mathcal C\). Then the word problem for \(G\) has generic-case complexity in \(\mathcal C\). Moreover, if \(\overline H\) is non-amenable then the generic-case complexity of the word problem for \(G\) in strongly in \(\mathcal C\). The result is applicable to a broad class of groups; in particular, one can use that the word problem for a word-hyperbolic group is solvable in linear time, the word problem for a linear group over rational numbers is solvable in cubic time, and that any group that embeds \(F_2\) is non-amenable. A generalization of the result to the membership problem is given. Also, it is shown that if \(G\) has infinite Abelianization then the generic-case complexity of the conjugacy problem for \(G\) is linear time. The proofs are based on the known theory of random walks on regular graphs.