On subset sum problem in branch groups

DOI10.46298/JGCC.2020.12.1.6541MaRDI QIDQ6342194zbMATH OpenFDO

Authors Andrey Nikolaev, Alexander Ushakov

Publication date 4 June 2020

Full work available at URL https://doi.org/10.46298/JGCC.2020.12.1.6541

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Geometric group theory (20F65)

Abstract: 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.

This page was built for publication: On subset sum problem in branch groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6342194)