O33a — NP-hardness of binary quadratic Diophantine solvability

Definitions and mathematical statement

An input is a binary-encoded sextuple $(a,b,c,d,e,f)\in{\mathbb{Z}}^6$, promised to satisfy \[ \Delta=b^2-4ac\ne t^2\quad\text{for every }t\in{\mathbb{Z}}. \] The promise includes negative discriminants; no positivity or nonsingularity condition beyond the stated nonsquare promise is added. A yes-instance satisfies \[ \exists x,y\in{\mathbb{Z}},\qquad ax^2+bxy+cy^2+dx+ey+f=0. \] The variables are unrestricted integers, not required to be nonnegative or bounded.

The question is NP-hardness of this promise decision problem. Under the conventional polynomial-time many-one interpretation, for every language $L\in\mathrm{NP}$ there must be a polynomial-time map $r$ sending every input string to a sextuple satisfying the nonsquare promise, with \[ w\in L\iff r(w)\text{ has an integral solution}. \] In particular, a reduction must preserve the promise for no-instances as well as yes-instances. Membership in NP, or NP-completeness, is not itself requested.

The supplied research summary labels this solved by Manders--Adleman (1978), citing NP-completeness of binary quadratics and the subfamily $Ax^2+By=C$. But that subfamily has quadratic coefficients $a=A,b=c=0$, hence $\Delta=0$, a square, so it is excluded by this problem's promise. The summary's additional claim that their reduction handles nonsquare discriminants is not accompanied by a reduction or precise theorem. Its integer-variable scope must also be checked rather than importing a nonnegative-variable solvability result. Thus the cited subfamily alone does not certify the promised NP-hardness, and the stored solved assessment remains a source-verification issue.

Short English statement

Is unrestricted integer solvability of a binary quadratic equation NP-hard when its quadratic discriminant is promised nonsquare? The supplied cited linear-in-one-variable subfamily has square discriminant and does not by itself resolve the promised problem.

Sources

• Local UnsolvedMath registry, permanent ID $8400037$, exact source code catalogue entry, original label O33a.
• Leonard Adleman and Kevin McCurley, Open Problems in Number Theory Complexity II (1994), O33a, source page 22 / LNCS page 312; https://mccurley.org/papers/open.ps.gz. Recorded access 2026-07-29; extraction recorded as PDF recovered against coauthor PostScript.
• Manders and Adleman, "NP-complete decision problems for binary quadratics" (1978), as supplied in the research summary. No full publication details, variable-domain statement, or nonsquare-discriminant reduction are included.