Download PDFOpen PDF in browserCurrent version

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

EasyChair Preprint 9354, version 13

6 pagesDate: September 10, 2023

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

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@booklet{EasyChair:9354,
  author    = {Frank Vega},
  title     = {SAT is as Hard as Solving Homogeneous Diophantine Equation of Degree Two},
  howpublished = {EasyChair Preprint 9354},
  year      = {EasyChair, 2023}}
Download PDFOpen PDF in browserCurrent version