La réduction du problème de factorisation entier à un problème NP-complet

Question

J'ai du mal à comprendre la relation entre NP-intermédiaire et NP-complet. Je sais que si P! = NP basée sur le théorème, il existe une classe de langues dans NP de Ladner, mais pas en P ou en NP-complet. Chaque problème NP peut être réduit à un problème NP-complet, mais je ne l'ai pas vu des exemples pour réduire un problème NPI soupçonné (comme factorisation) dans un problème NP-complet. Quelqu'un sait-il d'un exemple ou d'une autre NPI-> réduction NPC?

Answer 1

Par exemple, il y a une réduction classique nette d'affacturage de SAT qui est aussi une source d'instances SAT « durs » présumés. Fondamentalement, on utilise EE idées pour la multiplication binaire codé dans le circuit SAT. Considérez multiplication binaire comme un ajout d'une série de multiplicandes décalée vers la gauche, chaque « masqué » (ANDed) par les bits d'un multiplicateur. Les additions peuvent être réalisées par un circuit d'addition binaire qui est une série d'additionneurs complets.

Un premier cycle talentueux pourrait construire cet algorithme. Je ne sais pas où il a été proposé ou mis en œuvre dans la littérature. Je serais intéressé d'entendre toutes les références.

Voir par exemple Ce Satisfy: Une tentative pour résoudre le premier factorisation en utilisant Satisfiabilité solveurs par Stefan Schoenmackers et Anna Cavender qu'elle prévoit en détail. De plus, le DIMACS SAT défi à partir de la fin 90 avaient des cas d'affacturage qui ont été générés par certains chercheurs, mais peut-être l'algorithme n'a pas été rédigé dans un document séparement au cours de cette époque.

Answer 2

Pour être absolument clair, entier factorisation est pas connu pour être NP-intermédiaire, juste soupçonné d'être fondée sur l'absence soit la preuve NP-complet ou algorithme polynomial (malgré beaucoup de mettre de travail dans les deux). Je ne sais pas de problème naturel (à savoir non construit par Ladner pour la preuve) qui est certainement NP-intermédiaire si P et NP sont différents.

D'accord, après avertissement, Graphique Isomorphisme est un autre candidat probable pour un problème naturel NP-intermédiaire. Il y a d'une simple réduction du temps polynomiale à partir de Isomorphisme sous-graphe - il suffit de laisser les graphiques même! Graphique Isomorphisme est juste le cas particulier de la sous-graphe Isomorphisme où les deux graphiques ont la même taille. La touche finale est que sous-graphe Isomorphisme NP-complet.

En dehors de cela, il y a toujours bien sûr la réduction pas si d'information promise par le Cook- Levin théorème , nous avions su que tout problème NP-intermédiaire a une machine de Turing non déterministes polynomiale temps qui décide, et nous pouvons convertir en une instance de SAT (suffit de construire le TM!).