论文标题
代数方程式系统系统的解释问题
The Diophantine problem for systems of algebraic equations with exponents
论文作者
论文摘要
考虑公式$q_1α^{x_1}+\ dots+q_kα^{x_k} = q $，带常数$α\ in \ in \ intlline {\ mathbb {q}} \ setMinus \ setminus \ {0,1 \} $， $ q_1，\ ldots，q_k，q \ in \ overline {\ mathbb {q}} $ and unknowns $ x_1，\ ldots，x_k $，在本文中称为\ emph {angebraic emph {emph {angebraic方程式}。我们证明，确定给定方程是否具有整数解决方案的问题是$ \ textbf {np} $ - 完成，并且方程系统的同样存在（无论是$α$是固定还是作为输入的一部分给出）。此外，我们描述了带有指数的代数方程系统的所有解决方案集，并证明它是半线性的。
Consider the equation $q_1α^{x_1}+\dots+q_kα^{x_k} = q$, with constants $α\in \overline{\mathbb{Q}} \setminus \{0,1\}$, $q_1,\ldots,q_k,q\in\overline{\mathbb{Q}}$ and unknowns $x_1,\ldots,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 $\textbf{NP}$-complete, and that the same holds for systems of equations (whether $α$ 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.
