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.6541
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.

    https://doi.org/10.46298/jgcc.2020.12.1.6541
    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
    Licence: arXiv.org - Non-exclusive license to distribute

    Linked publications - datasets - softwares

    Source : ScholeXplorer IsRelatedTo DOI 10.1515/gcc-2017-0006
    • 10.1515/gcc-2017-0006
    • 10.1515/gcc-2017-0006
    Knapsack problem for nilpotent groups

    Share and export

    Consultation statistics

    This page has been seen 709 times.
    This article's PDF has been downloaded 332 times.