ON THE SUBSET SUM PROBLEM IN BRANCH GROUPS

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We consider a group-theoretic analogue of the classical subset sum problem. In this brief note, we show that the subset sum problem is NP-complete in the first Grigorchuk group. More generally, we show NP-hardness of that problem in weakly regular branch groups, which implies NP-completeness if the group is, in addition, contracting.

Original languageEnglish
JournalGroups, Complexity, Cryptology
Volume12
Issue number1
DOIs
StatePublished - 2020

Keywords

  • Grigorchuk group
  • NP-completeness
  • branch groups
  • subset sum problem

Fingerprint

Dive into the research topics of 'ON THE SUBSET SUM PROBLEM IN BRANCH GROUPS'. Together they form a unique fingerprint.

Cite this