TY - JOUR
T1 - The Diophantine problem for systems of algebraic equations with exponents
AU - Mandel, Richard
AU - Ushakov, Alexander
N1 - Publisher Copyright:
© 2023 Elsevier Inc.
PY - 2023/12/15
Y1 - 2023/12/15
N2 - Consider the equation q1αx1+…+qkαxk=q, with constants α∈Q‾∖{0,1}, q1,…,qk,q∈Q‾ and unknowns x1,…,xk, referred to in this paper as an algebraic equation with exponents. We prove that the problem to decide if a given equation has an integer solution is 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.
AB - Consider the equation q1αx1+…+qkαxk=q, with constants α∈Q‾∖{0,1}, q1,…,qk,q∈Q‾ and unknowns x1,…,xk, referred to in this paper as an algebraic equation with exponents. We prove that the problem to decide if a given equation has an integer solution is 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.
KW - Algebraic equations
KW - Complexity
KW - Diophantine problem
KW - Exponents
KW - NP-completeness
KW - Systems of equations
UR - http://www.scopus.com/inward/record.url?scp=85171991281&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85171991281&partnerID=8YFLogxK
U2 - 10.1016/j.jalgebra.2023.08.025
DO - 10.1016/j.jalgebra.2023.08.025
M3 - Article
AN - SCOPUS:85171991281
SN - 0021-8693
VL - 636
SP - 779
EP - 803
JO - Journal of Algebra
JF - Journal of Algebra
ER -