Knapsack problems in groups

DOI10.1090/S0025-5718-2014-02880-9zbMath1392.68207arXiv1302.5671MaRDI QIDQ5496223

No author found.

Publication date: 30 January 2015

Published in: Mathematics of Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1302.5671

zbMATH Keywords

nilpotent groupshyperbolic groupsknapsack problemmetabelian groupsBaumslag-Solitar groupThompson's group \(F\)subset sum problembounded subgroup membership problemBaumslag's metabelian group

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

20F18: Nilpotent groups

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

20F67: Hyperbolic groups and nonpositively curved groups

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Unnamed Item, Unnamed Item, Unnamed Item, Magnus embedding and algorithmic properties of groups 𝐹/𝑁^{(𝑑)}, Knapsack in hyperbolic groups, Complexity of word problems for HNN-extensions, Complexity of word problems for HNN-extensions, Decidability problem for exponential equations in finitely presented groups, Knapsack and the power word problem in solvable Baumslag–Solitar groups, The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete, Non-commutative lattice problems, Knapsack problem for nilpotent groups, Knapsack problems in products of groups, The shortest kinship description problem, Knapsack in graph groups, The power word problem in graph products, Closure properties of knapsack semilinear groups, Hardness of approximation for knapsack problems, Subset sum problem in polycyclic groups, Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups, Knapsack Problems for Wreath Products

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tilings and submonoids of metabelian groups.
• Discriminating completions of hyperbolic groups
• Small cancellation theory and automatic groups
• On generalised free products
• The solvability problem for quadratic equations over free groups is NP-complete
• Distortion of wreath products in some finitely presented groups.
• The combinatorial structure of cocompact discrete hyperbolic groups
• The occurrence problem for extensions of Abelian groups by nilpotent groups
• Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
• Algebraic geometry over groups. I: Algebraic sets and ideal theory
• Introductory notes on Richard Thompson's groups
• Irreducible affine varieties over a free group. I: Irreducibility of quadratic equations and Nullstellensatz
• Homomorphism diagrams of surface groups
• Isoperimetric and isodiametric functions of groups
• Coxeter groups, 2-completion, perimeter reduction and subgroup separability.
• Occurrence problem for free solvable groups
• Membership problem in groups acting freely on \(\mathbb N^n\)-trees.
• Growth of finitely generated solvable groups and curvature of Riemannian manifolds
• Random van Kampen diagrams and algorithmic problems in groups
• SOLVING THE WORD PROBLEM IN REAL TIME
• A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem
• Thompson’s Group and Public Key Cryptography
• Subgroups of small Cancellation Groups
• Equations in the Q-completion of a torsion-free hyperbolic group
• EXPONENTIAL GROUPS 2: EXTENSIONS OF CENTRALIZERS AND TENSOR COMPLETION OF CSA-GROUPS
• Subgroups of finitely presented metabelian groups
• FINITE SUBGROUPS OF HYPERBOLIC GROUPS
• LENGTH AND AREA FUNCTIONS ON GROUPS AND QUASI-ISOMETRIC HIGMAN EMBEDDINGS
• The word and geodesic problems in free solvable groups
• Automorphism groups of relatively free groups
• FULLY RESIDUALLY FREE GROUPS AND GRAPHS LABELED BY INFINITE WORDS
• A Finitely Presented Metabelian Group with a Free Abelian Derived Group of Infinite Rank
• Hiding information and signatures in trapdoor knapsacks
• Asymptotic cones and quasi-isometry invariants for hyperbolic metric spaces