TY - JOUR
T1 - Quadratic equations in metabelian Baumslag-Solitar groups
AU - Mandel, Richard
AU - Ushakov, Alexander
N1 - Publisher Copyright:
© 2023 World Scientific Publishing Company.
PY - 2023/9/1
Y1 - 2023/9/1
N2 - For a finitely generated group G, the Diophantine problem over G is the algorithmic problem of deciding whether a given equation W(z1,z2,...,zk) = 1 (perhaps restricted to a fixed subclass of equations) has a solution in G. In this paper, we investigate the algorithmic complexity of the Diophantine problem for the class of quadratic equations over the metabelian Baumslag-Solitar groups BS(1,n). We prove that this problem is NP-complete whenever n≠ ± 1, and determine the algorithmic complexity for various subclasses (orientable, nonorientable, etc.) of .
AB - For a finitely generated group G, the Diophantine problem over G is the algorithmic problem of deciding whether a given equation W(z1,z2,...,zk) = 1 (perhaps restricted to a fixed subclass of equations) has a solution in G. In this paper, we investigate the algorithmic complexity of the Diophantine problem for the class of quadratic equations over the metabelian Baumslag-Solitar groups BS(1,n). We prove that this problem is NP-complete whenever n≠ ± 1, and determine the algorithmic complexity for various subclasses (orientable, nonorientable, etc.) of .
KW - Baumslag-Solitar groups
KW - Diophantine problems
KW - Metabelian groups
KW - NP-completeness
UR - http://www.scopus.com/inward/record.url?scp=85169513184&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85169513184&partnerID=8YFLogxK
U2 - 10.1142/S0218196723500558
DO - 10.1142/S0218196723500558
M3 - Article
AN - SCOPUS:85169513184
SN - 0218-1967
VL - 33
SP - 1195
EP - 1216
JO - International Journal of Algebra and Computation
JF - International Journal of Algebra and Computation
IS - 6
ER -