6
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\begingroup$ 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$. $\endgroup$ – Dmitry Aug 17 '20 at 3:38
  • $\begingroup$ @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? $\endgroup$ – DUO Labs Aug 17 '20 at 3:42
  • 2
    $\begingroup$ 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. $\endgroup$ – Dmitry Aug 17 '20 at 4:02
  • 2
    $\begingroup$ 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. $\endgroup$ – plop Aug 17 '20 at 12:56
  • 1
    $\begingroup$ @Dmitry Your value for $B$ had only two factors $75363141341345632452454252455353=11×6851194667395057495677659314123$. See also the comment above. $\endgroup$ – plop Aug 17 '20 at 13:14
9
$\begingroup$

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<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}$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.