DocumentCode :
3168202
Title :
On The Complexity Of Matrix Group Problems I
Author :
Babai, Lászío ; Szemerédi, Endre
Author_Institution :
Eotvos University
fYear :
1984
fDate :
24-26 Oct. 1984
Firstpage :
229
Lastpage :
240
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1984. 25th Annual Symposium on
Conference_Location :
Singer Island, FL
ISSN :
0272-5428
Print_ISBN :
0-8186-0591-X
Type :
conf
DOI :
10.1109/SFCS.1984.715919
Filename :
715919
Link To Document :
بازگشت