Quadratic equations in metabelian Baumslag-Solitar groups

Richard Mandel, Alexander Ushakov

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

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 .

Original languageEnglish
Pages (from-to)1195-1216
Number of pages22
JournalInternational Journal of Algebra and Computation
Volume33
Issue number6
DOIs
StatePublished - 1 Sep 2023

Keywords

  • Baumslag-Solitar groups
  • Diophantine problems
  • Metabelian groups
  • NP-completeness

Fingerprint

Dive into the research topics of 'Quadratic equations in metabelian Baumslag-Solitar groups'. Together they form a unique fingerprint.

Cite this