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 -
On subset sum problem in branch groups

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.

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


Consultation statistics

This page has been seen 465 times.
This article's PDF has been downloaded 230 times.