33 citations · 92 across the 24 of their papers we have counts for
35 papers
Complexity of Spherical Equations in Finite Groups
Caroline Mattes, Alexander Ushakov, Armin Weiß
In this paper we investigate computational properties of the Diophantine problem for spherical equations in some classes of finite groups. We classify the complexity of different v…
Quadratic equations in metabelian Baumslag-Solitar groups
Richard Mandel, Alexander Ushakov
For a finitely generated group , the \emph{Diophantine problem} over is the algorithmic problem of deciding whether a given equation (perhaps res…
The Diophantine problem for systems of algebraic equations with exponents
Richard Mandel, Alexander Ushakov
Consider the equation , with constants , and unknowns $x_1…
Linear time algorithm for the conjugacy problem in the first Grigorchuk group
Mitra Modi, Mathew Seedhom, Alexander Ushakov
We prove that the conjugacy problem in the first Grigorchuck group can be solved in linear time. Furthermore, the problem to decide if a list of elements c…
On subset sum problem in branch groups
Andrey Nikolaev, Alexander Ushakov
We consider a group-theoretic analogue of the classic subset sum problem. In this brief note, we show that the subset sum problem is NP-complete in the first Grigorchuk group. More…
Orientable quadratic equations in free metabelian groups
Igor Lysenok, Alexander Ushakov
We prove that the Diophantine problem for orientable quadratic equations in free metabelian groups is decidable and furthermore, NP-complete. In the case when the number of variabl…