O33b — Randomized NP-hardness of binary quadratic Diophantine solvability

Definitions and mathematical statement

The source asks whether the "same binary quadratic Diophantine solvability problem" is NP-hard under randomized reductions. Its antecedent problem is not supplied. A binary quadratic input might specify an integer polynomial in two variables, but the exact equation, coefficient restrictions, variable domain, and size constraints are essential; integer, nonnegative-integer, and bounded-solution versions cannot be silently identified.

Once the intended decision language $L$ is fixed, NP-hardness under polynomial-time randomized many-one reductions in one common bounded-error sense means: for every $A\in\mathrm{NP}$ there is a randomized polynomial-time map $R$ such that for every input $x$, \[ \Pr_r\left[(x\in A)\Longleftrightarrow(R(x;r)\in L)\right]\geq\frac23. \] The source does not specify many-one versus oracle reductions or bounded-error versus zero-error conventions, so this is explanatory rather than a verified exact reduction model. A deterministic polynomial-time many-one reduction is a special case of the displayed randomized model.

The supplied summary attributes a deterministic NP-completeness result to Manders--Adleman (1978) and says it settles this item. That implication requires verifying that their problem is exactly the missing antecedent language; the record does not provide enough information to do so. No particular quadratic equation is invented to fill the gap.

Short English statement

Is the source's binary quadratic Diophantine decision problem NP-hard using randomized reductions? The exact solvability problem and reduction convention are missing, so the supplied deterministic-hardness attribution cannot be matched without the preceding source item.

Sources

• Leonard Adleman and Kevin McCurley, Open Problems in Number Theory Complexity II (1994), O33b, source page 22 / LNCS page 312, https://mccurley.org/papers/open.ps.gz; accessed 2026-07-29. The provenance records PDF text recovered against the coauthor-hosted PostScript.
• Manders--Adleman (1978), as the deterministic NP-completeness attribution in the supplied research summary; no theorem statement or complete publication citation is given.
• Local registry data/unsolvedmath/problems.json, permanent UnsolvedMath ID $8400038$, source code catalogue entry, O33b --- Randomized NP-hardness of binary quadratic Diophantine solvability. Dataset attribution: Ulam AI and the UnsolvedMath Contributors.