# Is “Solving two-variable quadratic polynomials over the Integers” is an NP-Complete Problem?

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.

• Did you try to input $A,B,C$ of order, for example, $10^{100}$? Surely, you can solve this problem in time polynomial of $A,B,C$. But the algorithm is polynomial if it is polynomial of the length of the input, i.e. the number of digits in $A,B,C$. – Dmitry Aug 17 '20 at 3:38
• @Dmitry But I don't understand: can't you generate polynomials $x=P_1(n), \, y=P_2(n), \, n \in \mathbb{Z}$, find the solution set for $x \geq 0, \, y \geq 0$, and see if there's integers in that? – DUO Labs Aug 17 '20 at 3:42
• You have $y = \frac 1B (C - A x^2)$. For $y$ to be an integer, you must have $A x^2 \equiv C \pmod B$. Let $A = 1$, so you have to find a square root of $C \pmod B$, without knowing the factorization of $B$. I think this is the part which is NP-hard. – Dmitry Aug 17 '20 at 4:02
• Even if factoring $B$ were easy, what can produce many choices that need to be analysed are the $\pm$ signs of the square roots of $C$ modulo the factors of $B$. A reduction of SUBSET SUM to this problem encodes the input set and the target in $A,B,C$ and the selection of the subset in the selection of these signs. – plop Aug 17 '20 at 12:56
• @Dmitry Your value for $B$ had only two factors $75363141341345632452454252455353=11×6851194667395057495677659314123$. See also the comment above. – plop Aug 17 '20 at 13:14

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

1. factor $$B=\prod_i q_i^{a_i}$$, where $$q_i$$ are different primes,
2. solve the congruences $$Ax^2-C\equiv 0\pmod{q_i}$$, which in the worst case have two solutions $$\pm t_i$$,
3. lift these solutions to solutions $$\pm\theta_i$$ of $$Ax^2-C\equiv 0\pmod{q_i^{a_i}}$$ and
4. glue these solutions, using the Chinese Remainder Theorem to get a solution of $$Ax^2-C\equiv0\pmod{B}$$. Note all the $$\pm$$ choices.

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, and $$|t|, 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}$$.

• Wow, such a well-written answer. Here is a much deserved +1 and accept! – DUO Labs Aug 17 '20 at 19:01