Knapsack problems in products of groups

Research output: Contribution to journalArticlepeer-review

29 Scopus citations

Abstract

The classic knapsack and related problems have natural generalizations to arbitrary (non-commutative) groups, collectively called knapsack-type problems in groups. We study the effect of free and direct products on their time complexity. We show that free products in certain sense preserve time complexity of knapsack-type problems, while direct products may amplify it. Our methods allow to obtain complexity results for rational subset membership problem in amalgamated free products over finite subgroups.

Original languageEnglish
Pages (from-to)96-108
Number of pages13
JournalJournal of Symbolic Computation
Volume74
DOIs
StatePublished - May 2016

Keywords

  • Bounded subgroup membership problem
  • Direct products
  • Free products
  • Hyperbolic groups
  • Knapsack problem
  • Nilpotent groups
  • Rational subset membership problem
  • Subset sum problem

Fingerprint

Dive into the research topics of 'Knapsack problems in products of groups'. Together they form a unique fingerprint.

Cite this