Knapsack problems in groups

Myasnikov, Alexei; Nikolaev, Andrey; Ushakov, Alexander

doi:10.1090/S0025-5718-2014-02880-9

Knapsack problems in groups
HTML articles powered by AMS MathViewer

by Alexei Myasnikov, Andrey Nikolaev and Alexander Ushakov PDF

Math. Comp. 84 (2015), 987-1016 Request permission

Abstract:

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 $\mathbf {P}$-time decidable in hyperbolic groups and give various examples of finitely presented groups where the subset sum problem is $\mathbf {NP}$-complete.

References

J. M. Alonso, T. Brady, D. Cooper, V. Ferlini, M. Lustig, M. Mihalik, M. Shapiro, and H. Short, Notes on word hyperbolic groups, Group theory from a geometrical viewpoint (Trieste, 1990) World Sci. Publ., River Edge, NJ, 1991, pp. 3–63. Edited by Short. MR 1170363
Gilbert Baumslag, On generalised free products, Math. Z. 78 (1962), 423–438. MR 140562, DOI 10.1007/BF01195185
Gilbert Baumslag, A finitely presented metabelian group with a free abelian derived group of infinite rank, Proc. Amer. Math. Soc. 35 (1972), 61–62. MR 299662, DOI 10.1090/S0002-9939-1972-0299662-4
Gilbert Baumslag, Subgroups of finitely presented metabelian groups, J. Austral. Math. Soc. 16 (1973), 98–110. Collection of articles dedicated to the memory of Hanna Neumann, I. MR 0332999
Gilbert Baumslag, Alexei Myasnikov, and Vladimir Remeslennikov, Algebraic geometry over groups. I. Algebraic sets and ideal theory, J. Algebra 219 (1999), no. 1, 16–79. MR 1707663, DOI 10.1006/jabr.1999.7881
Gilbert Baumslag, Alexei Myasnikov, and Vladimir Remeslennikov, Discriminating completions of hyperbolic groups, Geom. Dedicata 92 (2002), 115–143. Dedicated to John Stallings on the occasion of his 65th birthday. MR 1934015, DOI 10.1023/A:1019687202544
O. V. Bogopol′skiĭ and V. N. Gerasimov, Finite subgroups of hyperbolic groups, Algebra i Logika 34 (1995), no. 6, 619–622, 728 (Russian, with Russian summary); English transl., Algebra and Logic 34 (1995), no. 6, 343–345 (1996). MR 1400705, DOI 10.1007/BF00739330
Noel Brady, Finite subgroups of hyperbolic groups, Internat. J. Algebra Comput. 10 (2000), no. 4, 399–405. MR 1776048, DOI 10.1142/S0218196700000236
R. M. Bryant and V. A. Roman′kov, Automorphism groups of relatively free groups, Math. Proc. Cambridge Philos. Soc. 127 (1999), no. 3, 411–424. MR 1713119, DOI 10.1017/S0305004199003898
V. K. Bulitko, Equations and inequalities in a free group and a free semigroup, Tul. Gos. Ped. Inst. Učen. Zap. Mat. Kaf. 2 Geometr. i Algebra (1970), 242–252 (Russian). MR 0393235
J. W. Cannon, W. J. Floyd, and W. R. Parry, Introductory notes on Richard Thompson’s groups, Enseign. Math. (2) 42 (1996), no. 3-4, 215–256. MR 1426438
James W. Cannon, The combinatorial structure of cocompact discrete hyperbolic groups, Geom. Dedicata 16 (1984), no. 2, 123–148. MR 758901, DOI 10.1007/BF00146825
Sean Cleary, Distortion of wreath products in some finitely presented groups, Pacific J. Math. 228 (2006), no. 1, 53–61. MR 2263024, DOI 10.2140/pjm.2006.228.53
S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms, McGraw-Hill Science, 2006.
Cornelia Druţu, Cônes asymptotiques et invariants de quasi-isométrie pour des espaces métriques hyperboliques, Ann. Inst. Fourier (Grenoble) 51 (2001), no. 1, 81–97 (French, with English and French summaries). MR 1821069
Michael R. Garey and David S. Johnson, Computers and intractability, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness. MR 519066
S. M. Gersten and H. B. Short, Small cancellation theory and automatic groups, Invent. Math. 102 (1990), no. 2, 305–334. MR 1074477, DOI 10.1007/BF01233430
Mikhael Gromov, Groups of polynomial growth and expanding maps, Inst. Hautes Études Sci. Publ. Math. 53 (1981), 53–73. MR 623534
Mikhael Gromov, Hyperbolic groups, Essays in Group Theory, MSRI Publications, vol. 8, Springer, 1985, pp. 75–263.
Derek F. Holt and Sarah Rees, Solving the word problem in real time, J. London Math. Soc. (2) 63 (2001), no. 3, 623–639. MR 1825979, DOI 10.1017/S0024610701002083
Hans Kellerer, Ulrich Pferschy, and David Pisinger, Knapsack problems, Springer-Verlag, Berlin, 2004. MR 2161720, DOI 10.1007/978-3-540-24777-7
O. Kharlampovich, I. G. Lysënok, A. G. Myasnikov, and N. W. M. Touikan, The solvability problem for quadratic equations over free groups is NP-complete, Theory Comput. Syst. 47 (2010), no. 1, 250–258. MR 2643918, DOI 10.1007/s00224-008-9153-7
O. Kharlampovich and A. Myasnikov, Irreducible affine varieties over a free group. I. Irreducibility of quadratic equations and Nullstellensatz, J. Algebra 200 (1998), no. 2, 472–516. MR 1610660, DOI 10.1006/jabr.1997.7183
O. Kharlampovich, E. Lioutikova, and A. Myasnikov, Equations in the $\textbf {Q}$-completion of a torsion-free hyperbolic group, Trans. Amer. Math. Soc. 351 (1999), no. 7, 2961–2978. MR 1443195, DOI 10.1090/S0002-9947-99-02010-3
Markus Lohrey and Benjamin Steinberg, Tilings and submonoids of metabelian groups, Theory Comput. Syst. 48 (2011), no. 2, 411–427. MR 2763109, DOI 10.1007/s00224-010-9264-9
R. Merkle and M. Hellman, Hiding information and signatures in trapdoor knapsacks, Inform. Theory, IEEE Trans. 24 (1978), 525–530.
A. G. Miasnikov and A. Nikolaev, Verbal subgroups of hyperbolic groups have infinite width, preprint. Available at http://arxiv.org/abs/1107.3719, 2011.
A. G. Myasnikov and V. N. Remeslennikov, Exponential groups. II. Extensions of centralizers and tensor completion of CSA-groups, Internat. J. Algebra Comput. 6 (1996), no. 6, 687–711. MR 1421886, DOI 10.1142/S0218196796000398
A. G. Miasnikov, V. Remeslennikov, and D. Serbin, Regular free length functions on Lyndon’s free $\mathbb {Z}[t]$-group $f^{\mathbb {z}[t]}$, Algorithms, Languages, Logic, Contemporary Mathematics, vol. 378, American Mathematical Society, 2005, pp. 37–77.
Alexei G. Myasnikov, Vladimir N. Remeslennikov, and Denis E. Serbin, Fully residually free groups and graphs labeled by infinite words, Internat. J. Algebra Comput. 16 (2006), no. 4, 689–737. MR 2258835, DOI 10.1142/S0218196706003141
A. Myasnikov, V. Roman’kov, A. Ushakov, and A. Vershik, The word and geodesic problems in free solvable groups, Trans. Amer. Math. Soc. 362 (2010), no. 9, 4655–4682. MR 2645045, DOI 10.1090/s0002-9947-10-04959-7
A. G. Miasnikov, V. Shpilrain, and A. Ushakov, Non-commutative Cryptography and Complexity of Group-theoretic Problems, Mathematical Surveys and Monographs, AMS, 2011.
Alexei Myasnikov and Alexander Ushakov, Random van Kampen diagrams and algorithmic problems in groups, Groups Complex. Cryptol. 3 (2011), no. 1, 121–185. MR 2806084, DOI 10.1515/GCC.2011.006
K. A. Mihaĭlova, The occurrence problem for direct products of groups, Dokl. Akad. Nauk SSSR 119 (1958), 1103–1105 (Russian). MR 0100018
Andrey Nikolaev, Membership Problem in Groups Acting Freely on Non-Archimedean Trees, ProQuest LLC, Ann Arbor, MI, 2010. Thesis (Ph.D.)–McGill University (Canada). MR 2890071
Andrey Nikolaev and Denis Serbin, Membership problem in groups acting freely on $\Bbb {Z}^n$-trees, J. Algebra 370 (2012), 410–444. MR 2966848, DOI 10.1016/j.jalgebra.2012.07.038
A. M. Odlyzko, The rise and fall of knapsack cryptosystems, Cryptology and computational number theory (Boulder, CO, 1989) Proc. Sympos. Appl. Math., vol. 42, Amer. Math. Soc., Providence, RI, 1990, pp. 75–88. MR 1095552, DOI 10.1090/psapm/042/1095552
Alexander Yu. Ol′shanskii and Mark V. Sapir, Length and area functions on groups and quasi-isometric Higman embeddings, Internat. J. Algebra Comput. 11 (2001), no. 2, 137–170. MR 1829048, DOI 10.1142/S0218196701000401
A. Yu. Ol′shanskiĭ, Diagrams of homomorphisms of surface groups, Sibirsk. Mat. Zh. 30 (1989), no. 6, 150–171 (Russian); English transl., Siberian Math. J. 30 (1989), no. 6, 961–979 (1990). MR 1043443, DOI 10.1007/BF00970919
A. Yu. Ol′shanskiĭ, Periodic quotients of hyperbolic groups, Mat. Zametki 182 (1991), 543–567.
Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285
Christos H. Papadimitriou and Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Dover Publications, Inc., Mineola, NY, 1998. Corrected reprint of the 1982 original. MR 1637890
V. Remeslennikov, On finitely presented groups, Fourth All-Union Symposium on the Theory of Groups 1973 (Novosibirsk, USSR), 1973, pp. 164–169.
E. Rips, Subgroups of small cancellation groups, Bull. London Math. Soc. 14 (1982), no. 1, 45–47. MR 642423, DOI 10.1112/blms/14.1.45
N. S. Romanovskiĭ, The embedding problem for abelian-by-nilpotent groups, Sibirsk. Mat. Zh. 21 (1980), no. 2, 170–174, 239 (Russian). MR 569186
Mark V. Sapir, Jean-Camille Birget, and Eliyahu Rips, Isoperimetric and isodiametric functions of groups, Ann. of Math. (2) 156 (2002), no. 2, 345–466. MR 1933723, DOI 10.2307/3597195
Paul E. Schupp, Coxeter groups, 2-completion, perimeter reduction and subgroup separability, Geom. Dedicata 96 (2003), 179–198. MR 1956839, DOI 10.1023/A:1022155823425
Adi Shamir, A polynomial-time algorithm for breaking the basic Merkle-Hellman cryptosystem, IEEE Trans. Inform. Theory 30 (1984), no. 5, 699–704. MR 781265, DOI 10.1109/TIT.1984.1056964
V. Shpilrain and A. Ushakov, Thompson’s group and public key cryptography, Applied Cryptography and Network Security – ACNS 2005, Lecture Notes Comp. Sc., vol. 3531, Springer, 2005, pp. 151–164.
U. U. Umirbaev, The occurrence problem for free solvable groups, Algebra i Logika 34 (1995), no. 2, 211–232, 243 (Russian, with Russian summary); English transl., Algebra and Logic 34 (1995), no. 2, 112–124. MR 1362615, DOI 10.1007/BF00750164
A. Ushakov, Fundamental search problems in groups, Ph.D. thesis, CUNY/Graduate Center, 2005.
R. Venkatesan and S. Rajagopalan, Average case intractability of matrix and diophantine problems (extended abstract), STOC (S. Rao Kosaraju, Mike Fellows, Avi Wigderson, and John A. Ellis, eds.), ACM, 1992, pp. 632–642.
Joseph A. Wolf, Growth of finitely generated solvable groups and curvature of Riemannian manifolds, J. Differential Geometry 2 (1968), 421–446. MR 248688