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 : oai: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 data

    Source : ScholeXplorer HasVersion DOI 10.48550/arxiv.2006.03470
    • 10.48550/arxiv.2006.03470
    On subset sum problem in branch groups
    Nikolaev, Andrey ; Ushakov, Alexander ;

    Export

    BibTeX TEI DC OpenAIRE Crossref DOAJ zbJATS JSON

    Share

    Consultation statistics

    This page has been seen 592 times.
    This article's PDF has been downloaded 285 times.