Est-ce que "Résoudre des polynômes quadratiques à deux variables sur les entiers" est un problème NP-Complet ?

Aug 17 2020

Sur cet article de Wikipédia , ils affirment que, étant donné$A, B, C \geq 0, \; \in \mathbb{Z}$, décider s'il existe$x, \,y \geq 0, \, \in \mathbb{Z}$tel que$Ax^2+By-C=0$est NP-complet ?

Compte tenu de la facilité avec laquelle je peux en résoudre certains (avec rien d'autre que Wolfram), cela ne semble pas correct. Je suis sûr que c'est soit mal écrit, soit j'ai juste mal compris quelque chose.

Réponses

9 plop Aug 18 2020 at 01:30

Comme vous l'avez noté, résoudre cette équation diophantienne n'est pas compliqué, mathématiquement.

Il suffit de trouver les restes nécessaires$r$de$x$modulo$B$tel que$Ax^2-C$est un multiple de$B$, alors toutes les solutions entières sont de la forme$x=Bn+r$et$y=(C-Ax^2)/B=(C-A(Bn+r)^2)/B$.

Une façon de trouver les restes$r$est de

  1. facteur$B=\prod_i q_i^{a_i}$, où$q_i$sont des nombres premiers différents,
  2. résoudre les congruences$Ax^2-C\equiv 0\pmod{q_i}$, qui dans le pire des cas ont deux solutions$\pm t_i$,
  3. élever ces solutions à des solutions$\pm\theta_i$de$Ax^2-C\equiv 0\pmod{q_i^{a_i}}$et
  4. collez ces solutions, en utilisant le théorème du reste chinois pour obtenir une solution de$Ax^2-C\equiv0\pmod{B}$. Notez tous les$\pm$les choix.

Affacturage$B$est peut-être difficile, mais peut-être que ce n'est pas le cas. Ma connaissance dépassée est que personne ne sait. Aussi peut-être est-il aussi possible de trouver les restes$r$sans affacturage$B$. Ce que la preuve que j'ai vu exploite pour conclure que le problème est NP-complet, c'est la décision qui reste encore à prendre.

Le problème de décision original devient de vérifier si l'un des choix de$\pm$est tel que l'intervalle$x\geq0$, autrement dit$n\geq -r/B$, coupe (et intersection contient un entier) l'intervalle où$n$est telle que$y\geq0$. Par rapport à la taille de bit de$(A,B,C)$il peut y avoir beaucoup de restes$r$tester. Je ne quantifierai pas cette affirmation. Que la preuve de sa NP-complétude en témoigne.

Dans Moore et Mertens' The Nature of Computation , section 5.4.4, il y a une réduction (avec des parties restantes comme exercices) du problème de décision SUBSET SUM à ce problème de décision (appelons-le QDE).


Permettez-moi d'esquisser leur argument juste pour avoir un aperçu de la façon dont l'entrée de SUBSET SUM est encodée dans l'entrée de QDE et comment les choix de$\pm$correspondent aux sous-ensembles que l'on peut considérer dans SUBSET SUM. Peut-être que moi ou quelqu'un d'autre pourrons développer les détails plus tard.

SUBSET SUM obtient un ensemble (ou peut-être un multi-ensemble)$X=\{x_1,x_2,\ldots x_n\}\subset\mathbb{N}$et$t\in \mathbb{N}$et demande s'il existe un sous-ensemble$Y\subset X$telle que la somme de ses éléments soit$t$. Si l'on définit$S=2t-\sum_{k=1}^{n}x_k$alors SUBSET SUM est équivalent à l'existence de$\sigma_i\in\{-1,1\}$tel que$$S=\sum_{k=1}^{n}\sigma_kx_k$$

Ici nous avons déjà des choix de sous-ensembles encodés comme des choix de$\pm$.

Prise$m$tel que$2^m>\sum_{k=1}^{n}x_k$cette équation est équivalente à$$S\equiv \sum_{k=1}^{n}\sigma_kx_k\pmod{2^m}$$Si nous choisissons$q_1,q_2,...,q_n$nombres impairs relativement premiers (les premiers nombres premiers impairs suffisent), le théorème du reste chinois garantit qu'il y a$\theta_1,\theta_2,\ldots,\theta_n$tel que

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

La$\theta_i$seront, pour le problème QDE à créer, les solutions$\theta_i$que nous avons mentionné au début.

Le premier groupe de ces congruences implique que SUBSET SUM est équivalent à$$S\equiv \sum_{k=1}^{n}\sigma_k\theta_k\pmod{2^m}\qquad\qquad(*)$$

Maintenant ils construisent l'équation quadratique, dont la solubilité est équivalente à la solubilité de cette congruence.

Ils définissent$H=\sum_{k=1}^n\theta_k$et$K=\prod_{k=1}^{n}q_k^m$. Observez que tout$x$de la forme$$x=\sum_{k=1}^{n}\sigma_k\theta_k$$satisfait$$H^2-x^2\equiv0\pmod{K}$$

Ensuite, à travers une paire d'exercices, ils expliquent pourquoi il y a des choix pour choisir$q_i$et un$\lambda_1$assez grand pour que$2H<K$, et$|t|<H$, et s'assurer que$(*)$a une solution si et seulement si l'équation diophantienne quadratique

$$\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$$

a une solution$x,y\geq0$.

Remarquez comment cette équation se réécrit comme

$$\lambda_12^{m+1}(H^2-x^2)-K(S^2-x^2)=2^{m+1}Ky,$$

Les choix effectués dans les détails techniques sont tels que lorsqu'il existe une solution$x,y\geq0$pour cette équation c'est toujours le cas que$H^2-x^2$est déjà connu pour être un multiple de$K$et$S^2-x^2=(S+x)(S-x)$un multiple de$2^{m+1}$.