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

EasyChair Preprint no. 9354, version 13

Abstract

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 optimization without constraints and 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

@Booklet{EasyChair:9354,
  author = {Frank Vega},
  title = {SAT is as Hard as Solving Homogeneous Diophantine Equation of Degree Two},
  howpublished = {EasyChair Preprint no. 9354},

  year = {EasyChair, 2023}}