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
Additional Information
- Alexei Myasnikov
- Affiliation: Stevens Institute of Technology, Hoboken, New Jersey 07030
- Email: amiasnik@stevens.edu
- Andrey Nikolaev
- Affiliation: Stevens Institute of Technology, Hoboken, New Jersey 07030
- Email: anikolae@stevens.edu
- Alexander Ushakov
- Affiliation: Stevens Institute of Technology, Hoboken, New Jersey 07030
- MR Author ID: 788960
- Email: aushakov@stevens.edu
- Received by editor(s): March 29, 2012
- Received by editor(s) in revised form: February 19, 2013, June 7, 2013, and July 1, 2013
- Published electronically: July 30, 2014
- Additional Notes: The work of the first and third authors was partially supported by NSF grant DMS-0914773.
- © Copyright 2014 American Mathematical Society
- Journal: Math. Comp. 84 (2015), 987-1016
- MSC (2010): Primary 03D15, 20F65, 20F10
- DOI: https://doi.org/10.1090/S0025-5718-2014-02880-9
- MathSciNet review: 3290972