Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.08589 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913597579329536 |
|---|---|
| author | Ushakov, Alexander Weiers, Chloe |
| author_facet | Ushakov, Alexander Weiers, Chloe |
| contents | In this paper we study the complexity of solving quadratic equations in the lamplighter group. We give a complete classification of cases (depending on genus and other characteristics of a given equation) when the problem is $\mathbf{NP}$-complete or polynomial-time decidable. We notice that the conjugacy problem can be solved in linear time. Finally, we prove that the problem belongs to the class $\mathbf{XP}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_08589 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Quadratic equations in the lamplighter group Ushakov, Alexander Weiers, Chloe Group Theory 20F16, 20F10, 68W30 In this paper we study the complexity of solving quadratic equations in the lamplighter group. We give a complete classification of cases (depending on genus and other characteristics of a given equation) when the problem is $\mathbf{NP}$-complete or polynomial-time decidable. We notice that the conjugacy problem can be solved in linear time. Finally, we prove that the problem belongs to the class $\mathbf{XP}$. |
| title | Quadratic equations in the lamplighter group |
| topic | Group Theory 20F16, 20F10, 68W30 |
| url | https://arxiv.org/abs/2401.08589 |