{"docId":6541,"paperId":6541,"url":"https:\/\/gcc.episciences.org\/6541","doi":"10.46298\/jgcc.2020.12.1.6541","journalName":"journal of Groups, complexity, cryptology","issn":"","eissn":"1869-6104","volume":[{"vid":391,"name":"Volume 12, Issue 1"}],"section":[],"repositoryName":"arXiv","repositoryIdentifier":"2006.03470","repositoryVersion":3,"repositoryLink":"https:\/\/arxiv.org\/abs\/2006.03470v3","dateSubmitted":"2020-06-09 08:27:25","dateAccepted":"2020-06-24 11:00:04","datePublished":"2020-06-24 11:00:50","titles":["On subset sum problem in branch groups"],"authors":["Nikolaev, Andrey","Ushakov, Alexander"],"abstracts":["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"],"keywords":["Mathematics - Group Theory","Computer Science - Computational Complexity","03D15, 20F65, 20F10"]}