On subset sum problem in branch groups
| Autor: | Nikolaev, Andrey, Ushakov, Alexander |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Zdroj: | journal of Groups, complexity, cryptology, Volume 12, Issue 1 (June 24, 2020) gcc:6541 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.46298/jgcc.2020.12.1.6541 |
| Popis: | 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 |
| Databáze: | arXiv |
| Externí odkaz: |
|