Download PDFOpen PDF in browserCurrent versionSAT is as Hard as Solving Homogeneous Diophantine Equation of Degree TwoEasyChair Preprint no. 9354, version 146 pages•Date: September 11, 2023AbstractIn 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 NPcomplete 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 preconditions can turn this problem to be feasibly solved. Keyphrases: Boolean formula, completeness, complexity classes, polynomial time
