Title :
On The Complexity Of Matrix Group Problems I
Author :
Babai, Lászío ; Szemerédi, Endre
Author_Institution :
Eotvos University
Abstract :
We build a theory of black box groups, and apply it to matrix groups over finite fields. Elements of a black box group are encoded by strings of uniform length and group operations are performd by an oracle. Subgroups are given by a list of generators. We prove that for such subgroups, membership and divisor of the order are in NPB. (B is the group box oracle.) Under a plausible mathematical hypothesis on short presentations of finite simple groups, nom membership and exaact order will also be in NPB and thus in NPB ∩ NPB.
Keywords :
Complexity theory; Equations; Galois fields; Polynomials; Probability; Upper bound;
Conference_Titel :
Foundations of Computer Science, 1984. 25th Annual Symposium on
Conference_Location :
Singer Island, FL
Print_ISBN :
0-8186-0591-X
DOI :
10.1109/SFCS.1984.715919