On The Complexity Of Matrix Group Problems I

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 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.