Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
On this Wikipedia article, they claim that given $A, B, C \geq 0, \; \in \mathbb{Z}$, deciding whether there exist $x, \,y \geq 0, \, \in \mathbb{Z}$ such that $Ax^2+By-C=0$ is NP-complete?
Given by how easy I can solve some (with nothing but Wolfram), it doesn't seem right. I'm sure it's either written incorrectly or I'm just misunderstanding something.
As you noted, solving that Diophantine equation is not complicated, mathematically.
All is needed is to find the necessary remainders $r$ of $x$ modulo $B$ such that $Ax^2-C$ is a multiple of $B$, then all integer solutions are of the form $x=Bn+r$ and $y=(C-Ax^2)/B=(C-A(Bn+r)^2)/B$.
One way to find the remainders $r$ is to
Factoring $B$ is possibly hard, but maybe it isn't. My outdated knowledge is that nobody knows. Also maybe it is also possible to find the remainders $r$ without factoring $B$. What the proof that I saw exploits to conclude that the problem is NP-complete is the decision that still remains to be made.
The original decision problem becomes checking if one of the choices of $\pm$ is such that the interval $x\geq0$, in other words $n\geq -r/B$, intersects (and intersection contains an integer) the interval where $n$ is such that $y\geq0$. Compared to the bit size of $(A,B,C)$ there can be many remainders $r$ to test. I will not quantify this claim. Let the proof of its NP-completeness give evidence of it.
In Moore and Mertens' The Nature of Computation, section 5.4.4 there is a reduction (with parts left as exercises) of the SUBSET SUM decision problem to this decision problem (let's call it QDE).
Let me sketch their argument just to get a taste of how the input to SUBSET SUM is encoded in the input to QDE and how the choices of $\pm$ correspond to the subsets that one can consider in SUBSET SUM. Maybe I or someone else can expand the details later.
SUBSET SUM gets a set (or maybe a multi-set) $X=\{x_1,x_2,\ldots x_n\}\subset\mathbb{N}$ and $t\in \mathbb{N}$ and asks if there is a subset $Y\subset X$ such that the sum of its elements is $t$. If one defines $S=2t-\sum_{k=1}^{n}x_k$ then SUBSET SUM is equivalent to the existence of $\sigma_i\in\{-1,1\}$ such that $$S=\sum_{k=1}^{n}\sigma_kx_k$$
Here we have already choices of subsets encoded as choices of $\pm$.
Taking $m$ such that $2^m>\sum_{k=1}^{n}x_k$ this equation is equivalent to $$S\equiv \sum_{k=1}^{n}\sigma_kx_k\pmod{2^m}$$ If we choose $q_1,q_2,...,q_n$ relatively prime odd numbers (the first odd primes suffice), the Chinese Remainder theorem ensures that there are $\theta_1,\theta_2,\ldots,\theta_n$ such that
$$ \begin{align} \theta_k&\equiv x_k\pmod{2^m}\\\ \theta_i&\equiv0\pmod{\prod_{k=1,k\neq i}^{n}q_k^m}\\\ \theta_k&\not\equiv0\pmod{q_k} \end{align} $$
The $\theta_i$ will be, for the QDE problem to be created, the solutions $\theta_i$ that we mentioned at the beginning.
The first group of these congruences imply that SUBSET SUM is equivalent to $$S\equiv \sum_{k=1}^{n}\sigma_k\theta_k\pmod{2^m}\qquad\qquad(*)$$
Now they build the quadratic equation, which solubility is equivalent to the solubility of this congruence.
They define $H=\sum_{k=1}^n\theta_k$ and $K=\prod_{k=1}^{n}q_k^m$. Observe that any $x$ of the form $$x=\sum_{k=1}^{n}\sigma_k\theta_k$$ satisfies $$H^2-x^2\equiv0\pmod{K}$$
Then, through a pair of exercises, they argue why there are choices for picking $q_i$ and a $\lambda_1$ large enough such that $2H<K$, and $|t|<H$, and ensuring that $(*)$ has a solution if and only if the Quadratic Diophantine Equation
$$\underbrace{(\lambda_12^{m+1}+K)}_{A}x^2+\underbrace{2^{m+1}K}_{B}y-\underbrace{(\lambda_12^{m+1}H^2-KS^2)}_C=0$$
has a solution $x,y\geq0$.
Notice how this equation re-writes as
$$\lambda_12^{m+1}(H^2-x^2)-K(S^2-x^2)=2^{m+1}Ky,$$
The choices made in the technical details are such that when there is a solution $x,y\geq0$ for this equation it is always the case that $H^2-x^2$ is already known to be a multiple of $K$ and $S^2-x^2=(S+x)(S-x)$ a multiple of $2^{m+1}$.
