The Diophantine problem for systems of algebraic equations with exponents

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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of algebra 2023-12, Vol.636, p.779-803
Main Authors: Mandel, Richard, Ushakov, Alexander
Format: Article
Language:English
Subjects:
Algebraic equations
Complexity
Diophantine problem
Exponents
NP-completeness
Systems of equations
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0021-8693
1090-266X
DOI:10.1016/j.jalgebra.2023.08.025