On The Complexity Of Matrix Group Problems I

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 NP B . (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 NP B and thus in NP B ∩ NP B .