Quadratic equations in the lamplighter group
| Autor: | Ushakov, Alexander, Weiers, Chloe |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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}$. |
| Databáze: | arXiv |
| Externí odkaz: |
|