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
nilpotent groupshyperbolic groupsknapsack problemmetabelian groupsBaumslag-Solitar groupThompson's group \(F\)subset sum problembounded subgroup membership problemBaumslag's metabelian group
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
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