A polynomial-time theory of black box groups I
László Babai, Robert Beals · Cambridge University Press eBooks · 2013
We consider the asymptotic complexity of algorithms to manipulate matrix groups over finite fields. Groups are given by a list of generators. Some of the rudimentary tasks such as membership testing and computing the order are not expected to admit polynomial-time solutions due to number theoretic obstacles such as factoring integers and discrete logarithm. While these and other “abelian obstacles” persist, we demonstrate that the “nonabelian normal structure” of matrix groups over finite fields can be mapped out in great detail by polynomial-time randomized (Monte Carlo) algorithms. The methods are based on statistical results on finite simple groups. We indicate the elements of a project under way towards a more complete “recognition” of such groups in polynomial time. In particular, under a now plausible hypothesis, we are able to determine the names of all nonabelian composition factors of a matrix group over a finite field. Our context is actually far more general than matrix groups: most of the algorithms work for “black-box groups” under minimal assumptions. In a black-box group, the group elements are encoded by strings of uniform length, and the group operations are performed by a “black box.”