Comment peut-P =? NP améliorer entier factorisation

Question

Si $ {\ sf P} $ a en fait égal $ {\ sf NP} $, comment cela améliorer nos algorithmes entiers de facteur plus rapide. En d'autres termes, quel genre de perspicacité serait ce fait nous donner en entier la compréhension factorisation mieux?

Answer 1

Si $ P = NP $, et nous avons un algorithme qui peut résoudre le k-SAT problème en temps polynomial, alors entier factorisation peut être simplement réduite à k-SAT en décrivant l'affacturage comme un problème dans k-SAT.

Pour l'essentiel, il fonctionne comme suit: Vous faites un tas de variables représentant chacun des bits de $ p $ et $ q $, et $ n $. Ensuite, vous formulez le problème k-SAT $ p * q = n $. Puisque n $ est connu, vous pouvez définir ces valeurs. Ensuite, une affectation satisfaisant décrira un $ p $ valide et $ q $. Décrire la multiplication dans k-SAT, vous pouvez utiliser des algorithmes de multiplication connus et décrire est le circuit logique dans k-SAT. Pour plus d'informations sur la réduction de l'affacturage à k-SAT, voir .

En ce qui concerne l'affacturage meilleure compréhension, qui nécessiterait probablement plus de recherche et d'analyse de l'algorithme magique (qui peut résoudre les problèmes NP-complets en temps polynomial déterministe), et peut-être spécialisée à la formulation d'affacturage entier de problème k-SAT ( ce qui a évidemment une structure très particulière, en fonction de l'algorithme de multiplication utilisé).

Answer 2

Le problème de décision pour l'affacturage est $ \ mathsf {NP} $ et l'affacturage peut être réduit à dans le temps polynôme déterministe.

Si $ \ mathsf {P} = \ {mathsf NP} $, alors alors tout problème dans $ \ mathsf {NP} $ incluant l'affacturage aura un algorithme polynomial.

Notez que les plus connus des algorithmes déterministes / probabilistes pour l'affacturage au moment de prendre le temps exponentiel donc un algorithme polynomial serait une grande amélioration. Pour obtenir un sentiment de celui-ci, tenez compte d'un nombre à peu de 2000. On peut prendre plus de temps que tout le temps depuis le big bang, l'autre peut répondre en quelques millisecondes.