Download PDFOpen PDF in browserCurrent versionHomogeneous Diophantine Equation of Degree Two in NPCompleteEasyChair Preprint no. 9354, version 34 pages•Date: December 9, 2022AbstractP 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. Certainly, using the Hasse principle we may able to decide whether a homogeneous Diophantine equation of degree two has an integer solution: we are capable to reject an instance when there is no solution reducing the equation modulo p. 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
