A group family is a countable family B = {Bn}nΒΏ0 of ΓΏnite black-box groups, i.e., the elements of each group Bn are uniquely encoded as strings of uniform length (polynomial in n) and for each Bn the group operations are computable in time polynomial in n. In this paper we study the complexity of NP sets A which has the following property: the set of solutions for every x β A is a subgroup (or is the right coset of a subgroup) of a group B i(|x|) from a given group family B, where i is a polynomial. Such an NP set A is said to be deΓΏned over the group family B.
Decision problems like Graph Automorphism, Graph Isomorphism, Group Intersection, Coset Intersection, and Group Factorization for permutation groups give natural examples of such NP sets deΓΏned over the group family of all permutation groups. We show that any such NP set deΓΏned over permutation groups is low for PP and C =P.
As one of our main results we prove that NP sets deΓΏned over abelian black-box groups are low for PP. The proof of this result is based on the decomposition theorem for ΓΏnite abelian groups. As an interesting consequence of this result we obtain new lowness results: Membership Testing, Group Intersection, Group Factorization, and some other problems for abelian black-box groups are low for PP and C=P.
As regards the corresponding counting problem for NP sets over any group family of arbitrary black-box groups, we prove that exact counting of number of solutions is in FP AM . Consequently, none of these counting problems can be #P-complete unless PH collapses.