The Diophantine problem for systems of algebraic equations with exponents

Richard Mandel, Alexander Ushakov

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)779-803
Number of pages25
JournalJournal of Algebra
Volume636
DOIs
StatePublished - 15 Dec 2023

Keywords

  • Algebraic equations
  • Complexity
  • Diophantine problem
  • Exponents
  • NP-completeness
  • Systems of equations

Fingerprint

Dive into the research topics of 'The Diophantine problem for systems of algebraic equations with exponents'. Together they form a unique fingerprint.

Cite this