ON THE SUBSET SUM PROBLEM IN BRANCH GROUPS

Andrey Nikolaev; Alexander Ushakov

doi:10.46298/jgcc.2020.12.1.6541

ON THE SUBSET SUM PROBLEM IN BRANCH GROUPS

Department of Mathematical Sciences

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

We consider a group-theoretic analogue of the classical 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.

Original language	English
Journal	Groups, Complexity, Cryptology
Volume	12
Issue number	1
DOIs	https://doi.org/10.46298/jgcc.2020.12.1.6541
State	Published - 2020

Keywords

Grigorchuk group
NP-completeness
branch groups
subset sum problem

Access to Document

10.46298/jgcc.2020.12.1.6541

Cite this

@article{c936eb9dda724645bef33a8e68abc451,

title = "ON THE SUBSET SUM PROBLEM IN BRANCH GROUPS",

abstract = "We consider a group-theoretic analogue of the classical 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.",

keywords = "Grigorchuk group, NP-completeness, branch groups, subset sum problem",

author = "Andrey Nikolaev and Alexander Ushakov",

note = "Publisher Copyright: {\textcopyright} Andrey Nikolaev and Alexander Ushakov.",

year = "2020",

doi = "10.46298/jgcc.2020.12.1.6541",

language = "English",

volume = "12",

number = "1",

}

TY - JOUR

T1 - ON THE SUBSET SUM PROBLEM IN BRANCH GROUPS

AU - Nikolaev, Andrey

AU - Ushakov, Alexander

N1 - Publisher Copyright: © Andrey Nikolaev and Alexander Ushakov.

PY - 2020

Y1 - 2020

N2 - We consider a group-theoretic analogue of the classical 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.

AB - We consider a group-theoretic analogue of the classical 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.

KW - Grigorchuk group

KW - NP-completeness

KW - branch groups

KW - subset sum problem

UR - https://www.scopus.com/pages/publications/85161030246

UR - https://www.scopus.com/pages/publications/85161030246#tab=citedBy

U2 - 10.46298/jgcc.2020.12.1.6541

DO - 10.46298/jgcc.2020.12.1.6541

M3 - Article

AN - SCOPUS:85161030246

SN - 1867-1144

VL - 12

JO - Groups, Complexity, Cryptology

JF - Groups, Complexity, Cryptology

IS - 1

ER -

ON THE SUBSET SUM PROBLEM IN BRANCH GROUPS

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this