On the complexity of intersection and conjugacy problems in free groups

AbstractNielsen type arguments have been used to prove some problems in free group (e.g., the generalized word problem) [2] to be P-complete. In this paper we extend this approach. Having a Nielsen reduced set of generators for subgroups H and K one can solve a lot of intersection and conjugacy problems in polynomial time in a uniform way.We study the solvability of (i) ∃h ∈ H, k ∈ K: hx = yk in F, and (ii) ∃ w ∈ F: w̄l Hw = K characterize the set of solutions. This leads for (i) to an algorithm for computing a set of generators for H ∩ K (and a new proof that free groups have the Howson property). For (ii) this gives a fast solution of Moldavanskii's conjugacy problem; an algorithm for computing the normal hull of H then gives a representation of all solutions. All the algorithms run in polynomial time and the decision problems are proved to be P-complete under log-space reducibility