The Diophantine problem for systems of algebraic equations with exponents

Abstract

Consider the equation $q_1{\alpha }^{x_1}+\cdots +q_k{\alpha }^{x_k}=q$, with constants $\alpha \in \overline{\mathbb{Q}}\setminus \{0,1\}$, $q_1,\dots ,q_k,q\in \overline{\mathbb{Q}}$ and unknowns $x_1,\dots ,x_k$, referred to in this paper as an \emph{algebraic equation with exponents}. We prove that the problem to decide if a given equation has an integer solution is $\text{NP}$-complete, and that the same holds for systems of equations (whether $\alpha$ is fixed or given as part of the input). Furthermore, we describe the set of all solutions for a given system of algebraic equations with exponents and prove that it is semilinear.