Quadratic equations in the lamplighter group

Alexander Ushakov; Chloe Weiers

doi:10.1016/j.jsc.2024.102417

Quadratic equations in the lamplighter group

Alexander Ushakov, Chloe Weiers

Department of Mathematical Sciences

Stevens Institute of Technology

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Article number	102417
Journal	Journal of Symbolic Computation
Volume	129
DOIs	https://doi.org/10.1016/j.jsc.2024.102417
State	Published - 1 Jul 2025

Keywords

Conjugacy problem
Diophantine problem
Lamplighter group
NP-completeness
Quadratic equations
Spherical equations
Wreath product

Access to Document

10.1016/j.jsc.2024.102417

Cite this

@article{73c7a26383184b5b83784ea84c9bdccc,

title = "Quadratic equations in the lamplighter group",

abstract = "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.",

keywords = "Conjugacy problem, Diophantine problem, Lamplighter group, NP-completeness, Quadratic equations, Spherical equations, Wreath product",

author = "Alexander Ushakov and Chloe Weiers",

note = "Publisher Copyright: {\textcopyright} 2024 Elsevier Ltd",

year = "2025",

month = jul,

day = "1",

doi = "10.1016/j.jsc.2024.102417",

language = "English",

volume = "129",

}

TY - JOUR

T1 - Quadratic equations in the lamplighter group

AU - Ushakov, Alexander

AU - Weiers, Chloe

PY - 2025/7/1

Y1 - 2025/7/1

N2 - 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.

AB - 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.

KW - Conjugacy problem

KW - Diophantine problem

KW - Lamplighter group

KW - NP-completeness

KW - Quadratic equations

KW - Spherical equations

KW - Wreath product

UR - http://www.scopus.com/inward/record.url?scp=85211966243&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85211966243&partnerID=8YFLogxK

U2 - 10.1016/j.jsc.2024.102417

DO - 10.1016/j.jsc.2024.102417

M3 - Article

AN - SCOPUS:85211966243

SN - 0747-7171

VL - 129

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

M1 - 102417

ER -

Quadratic equations in the lamplighter group

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this