Nikolaev, Andrey and Ushakov, Alexander - 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: Nikolaev, Andrey and Ushakov, Alexander

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
Submitted on: June 9, 2020
Keywords: Mathematics - Group Theory,Computer Science - Computational Complexity,03D15, 20F65, 20F10


Share

Consultation statistics

This page has been seen 16 times.
This article's PDF has been downloaded 9 times.