Download PDFOpen PDF in browserCurrent versionSAT is as Hard as Solving Homogeneous Diophantine Equation of Degree TwoEasyChair Preprint 9354, version 55 pages•Date: March 7, 2023AbstractP versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? It was essentially mentioned in 1955 from a letter written by John Nash to the United States National Security Agency. However, a precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. 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 NPcomplete under the constraints that all solutions contain only positive integers which are actually residues of modulo a single positive integer. Keyphrases: Boolean formula, completeness, complexity classes, polynomial time
