Quadratic equations in metabelian Baumslag-Solitar groups

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 .