Andrey Nikolaev ; Alexander Ushakov - On subset sum problem in branch groups
gcc:6541 - journal of Groups, complexity, cryptology, June 24, 2020, Volume 12, Issue 1 - https://doi.org/10.46298/jgcc.2020.12.1.6541On subset sum problem in branch groupsArticle
Authors: Andrey Nikolaev ; Alexander Ushakov 
We consider a group-theoretic analogue of the classic 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.
Comment: v3: final version for journal of Groups, Complexity, Cryptology.
arXiv admin note: text overlap with arXiv:1703.07406
Source: arXiv.org:2006.03470
Volume: Volume 12, Issue 1
Published on: June 24, 2020
Accepted on: June 24, 2020
Submitted on: June 9, 2020
Keywords: Mathematics - Group Theory, Computer Science - Computational Complexity, 03D15, 20F65, 20F10
Classifications
Mathematics Subject Classification 20201
- 20E08 - Groups acting on trees
- 20F10 - Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
- 20F65 - Geometric group theory
- 68Q17 - Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
- 90C27 - Combinatorial optimization
Consultation statistics
This page has been seen 1424 times.
This article's PDF has been downloaded 1043 times.