2023/11/13 by Alexander Ushakov, Ushakov, Alexander, Chloe Weiers +1 · 1 citation
Computer Science · #20F10 #20F16 #68W30 #Cellular Automata and Applications #Coding theory and cryptography #FOS: Mathematics #Group Theory (math.GR) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2401.08589
openalex publication_date 2023/11/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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 XP.