Download PDFOpen PDF in browser

SAT is as Hard as Solving Homogeneous Diophantine Equation of Degree Two

EasyChair Preprint no. 9354, version 15

6 pagesDate: November 21, 2023


In mathematics, a Diophantine equation is a polynomial equation, usually involving two or more unknowns, such that the only solutions of interest are the integer ones. A homogeneous Diophantine equation is a Diophantine equation that is defined by a homogeneous polynomial. Solving a homogeneous Diophantine equation is generally a very difficult problem. However, homogeneous Diophantine equations of degree two are considered easier to solve. We prove that this decision problem is actually in NP-complete under the constraints that all solutions contain only positive integers which are actually residues of modulo 2. In addition, we show its optimization variant is equivalent to solving a problem of quadratic polynomial optimization without the restriction that the variables must be necessarily integers. This means that this optimization problem can be solved over the domains of real numbers with at most quadratic exponent and so, we expect these pre-conditions can turn this problem to be feasibly solved.

Keyphrases: Boolean formula, completeness, complexity classes, polynomial time

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
  author = {Frank Vega},
  title = {SAT is as Hard as Solving Homogeneous Diophantine Equation of Degree Two},
  howpublished = {EasyChair Preprint no. 9354},

  year = {EasyChair, 2023}}
Download PDFOpen PDF in browser