Une variante NP-complète de l'affacturage.

Le livre d’ Arora et Barak présente l’affacturage comme le problème suivant:

$\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$

Ils ajoutent, plus loin dans le chapitre 2, que le fait de supprimer le fait que est primordial rend ce problème NP-complet, bien que cela ne soit pas lié à la difficulté de factoriser des nombres. Il semble y avoir une réduction de SUBSETSUM, mais je me suis retrouvée coincée à le trouver. Une meilleure chance ici?$p$

EDIT 1er mars: La prime est pour la preuve de complétude utilisant une réduction déterministe de Karp (ou Cook).$NP$

Ce n'est pas tout à fait une réponse, mais c'est proche. Ce qui suit est la preuve que le problème est NP-difficile avec des réductions aléatoires.

Il existe une relation évidente à la somme de sous-ensembles qui est: supposons que vous connaissiez les facteurs de : , , , . Maintenant, vous voulez trouver un sous-ensemble de tel quep 1 p 2 … p k S p 1 … p $N$$p_1$$p_2$$\ldots$$p_k$$S$$p_1$ $\ldots$ $p_k$

Le problème lorsque vous essayez d'utiliser cette idée pour montrer que le problème est NP-difficile, c'est que si vous avez un problème de sous-somme avec les nombres , , , , vous ne pouvez pas nécessairement trouver des nombres premiers en temps polynomial tels que (où par , je veux dire approximativement proportionnel à). C'est un réel problème car, étant donné que le sous-ensemble somme n'est pas fortement NP-complet, vous devez trouver ces pour les entiers de grande taille .t 2 … t k log p i ∝ t i ∝ log p i t $t_1$$t_2$$\ldots$$t_k$$\log p_i \propto t_i$$\propto$$\log p_i$$t_i$

Supposons maintenant que nous avons besoin que tous les entiers d'un problème de somme de sous-ensembles soient compris entre et et que la somme soit approximativement . Le problème de la somme des sous-ensembles sera toujours NP-complet et toute solution sera la somme de entiers. Nous pouvons changer le problème de nombres entiers en réels si nous laissons être entre et , et au lieu d'exiger que la somme soit exactement , nous exigeons qu'elle soit entre et . Nous avons seulement besoin de spécifier nos chiffres à environ … t k x x ( 1 + 1 / k ) $t_1$ $\ldots$ $t_k$$x$$x(1+1/k)$k/2t ' i TiTi+$\frac{1}{2}\sum_i t_i$$k/2$$t'_i$$t_i$ sss+$t_i+\frac{1}{10k}$$s$$s$ 4logkBlogpiB+4log$s + \frac{1}{10}$$4 \log k$ plus de bits de précision pour le faire. Ainsi, si nous commençons par des nombres avec bits et que nous pouvons spécifier des nombres réels à environ bits de précision, nous pouvons effectuer notre réduction.$B$$\log p_i$$B + 4 \log k$

Maintenant, de wikipedia (via le commentaire de Hsien-Chih ci-dessous), le nombre de nombres premiers entre et est , donc si vous choisissez simplement nombres au hasard dans cette gamme, et les tester pour la primalité, avec une probabilité élevée obtenir un nombre premier dans le temps polynomial.T + T 5 / 8 θ ( T 5 / 8 / log T $T$$T+ T^{5/8}$$\theta(T^{5/8}/\log T)$

Essayons maintenant la réduction. Disons que nos sont tous bits longs. Si nous prenons de longueur bits, alors nous pouvons trouver un premier près de avec bits de précision. Ainsi, nous pouvons choisir pour que avec une précision de bits. Cela nous permet de trouver pour que avec une précision de bits. Si un sous-ensemble de ces nombres premiers se multiplie à quelque chose de proche de la valeur cible, il existe une solution aux problèmes de somme du sous-ensemble d'origine. Alors on laisse B T i 3 B p i T i 9 / 8 B T i connecte T i a t i 9 /$t_i$$B$$T_i$$3B$$p_i$$T_i$$9/8B$$T_i$$\log T_i \propto t_i$p i ≈ T i connecte p i a t i neuf /$9/8\, B$$p_i \approx T_i$$\log p_i \propto t_i$N = Π i p i L $9/8\,B$$N=\Pi_i p_i$ , choisissez et correctement, et nous avons une réduction aléatoire de la somme du sous-ensemble.$L$$U$

Je pense qu'il est lié au théorème de PCP (en particulier ).$NP = PCP[O(\log{n}), O(1)]$

Un extrait d'un article de Madhu :

... La notion selon laquelle un vérificateur peut effectuer n’importe quel calcul de temps polynomial enrichit considérablement la classe de théorèmes et de preuves et commence à proposer des méthodes hautement non triviales pour prouver des théorèmes. (Une conséquence immédiate est que nous pouvons supposer théorèmes / preuves / assertions / arguments sont des séquences binaires et nous le ferons désormais.) Par exemple, supposons que nous avons une affirmation (dire l'hypothèse de Riemann), et dire que nous pensons qu'il a preuve qui pourrait s’inscrire dans un article de 10 000 pages. La perspective de calcul indique que, étant donné et cette borne (10 000 pages), on peut calculer efficacement trois entiers positifs avec tels que soit vrai si et seulement siA N , L , U L ≤ U ≤ N A N L U N L $A$$A$$N, L, U$$L \leq U \leq N$$A$$N$a un diviseur entre et . Les entiers , et seront assez longs (leur écriture prendrait peut-être un million de pages), mais ils peuvent être produits de manière extrêmement efficace (en moins de temps que cela prendrait une imprimante pour imprimer tous ces entiers, qui est certainement au plus un jour ou deux). (Cet exemple spécifique est basé sur un résultat dû à Joe Kilian , communication personnelle) ...$L$$U$$N$$L$$U$

... bien au-delà de mes compétences en théorie de la complexité :-)

Il s'agit d'une idée de réduction déterministe efficace et informelle (qui peut être incomplète):

Fractran est un langage de programmation complet de Turing. Une version délimitée correctement des programmes Fractran devrait être réductible à la langue$\{\langle L, U, M \rangle \;|\; (\exists \text{ a positive integer } p \in \{L, \ldots, U\})[p | M]\}$

Par exemple, une version bornée pourrait demander si le nombre entier est produit dans la séquence de sortie d'un programme Fractran dans un certain nombre d'étapes (divisions) (c'est-à-dire ).M = N j ∗ F $M$$M=N_j * F_i$