On the Diophantine problem related to power circuits

Abstract

Myasnikov, Ushakov, and Won introduced power circuits in 2012 to construct a polynomial-time algorithm for the word problem in the Baumslag group, which has a non-elementary Dehn function. Power circuits are computational structures that support addition and the operation $(x,y)\mapsto x\cdot 2^y$ on integers. They also posed the question of decidability of the Diophantine problem over the structure $⟨{\mathbb{N}}_{>0};+,x\cdot 2^y,\le ,1⟩$, which is closely related to power circuits. In this paper, we prove that the Diophantine problem over this structure is undecidable.

Published in the journal of Groups, Complexity, Cryptology