Search

In this paper we further study properties of Magnus embedding, give a precise reducibility diagram for Dehn problems in groups of the form F / N ( d ) F/N^{(d)} , and provide a detailed answer to Problem 12.98 in The Kourovka notebook. We also show that most of the reductions are polynomial time reductions and can be used in practical computation.

We generalize the classical knapsack and subset sum problems to arbitrary groups and study the computational complexity of these new problems. We show that these problems, as well as the bounded submonoid membership problem, are P-time decidable in hyperbolic groups and give various examples of finitely presented groups where the subset sum problem is NP-complete., 28 pages, 12 figures