Download PDFOpen PDF in browserCurrent versionHomogeneous Diophantine Equation of Degree Two in NPCompleteEasyChair Preprint no. 9354, version 23 pages•Date: December 3, 2022AbstractIn 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 able 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 a residue of modulo a single positive integer. This problem remains in NPcomplete even when all the coefficients are nonnegative. Keyphrases: Boolean formula, completeness, complexity classes, polynomial time
