Réduire le problème de factorisation d'entier en un problème NP-Complete

17

J'ai du mal à comprendre la relation entre NP-intermédiaire et NP-complet. Je sais que si P! = NP basé sur le théorème de Ladner, il existe une classe de langages en NP mais pas en P ni en NP-Complete. Chaque problème dans NP peut être réduit à un problème NP-Complete, mais je n'ai vu aucun exemple de réduction d'un problème NPI suspecté (comme la factorisation entière) en un problème NP-Complete. Quelqu'un connaît-il un exemple de cela ou d'une autre réduction NPI-> NPC?

np-complete reductions factoring Nathan Jordan
la source
4
Par la définition de NP-exhaustivité, tout problème dans NP peut être réduit à n'importe quel problème NP-complet. En particulier, le théorème de Cook montre que SAT est NP-complet, et vous donne donc "explicitement" une telle réduction.
Yuval Filmus
1
@YuvalFilmus Je comprends qu'il existe une formalisation qu'une telle méthode existe, mais je cherchais une approche algorithmique plus concrète similaire à, disons, la réduction du problème du cycle hamiltonien au problème du voyageur de commerce. Dans lequel vous pouvez définir tous les poids de bord à 1 et exécuter TSP sur le graphique et vérifier si la distance parcourue est supérieure à | E |. Quelque chose comme ça, je suppose.
Nathan Jordan

Réponses:

11

Par exemple, il existe une nette réduction classique de l'affacturage vers SAT qui est également une source d'instances SAT "dures" présumées. Fondamentalement, on utilise des idées EE pour la multiplication binaire codée dans le circuit SAT. Considérez la multiplication binaire comme l'addition d'une série de multiplicands décalés vers la gauche, chacun "masqué" (ET) par les bits d'un multiplicateur. Les ajouts peuvent être effectués par un circuit d'addition binaire qui est une série d'additionneurs complets.

Un étudiant de premier cycle talentueux pourrait construire cet algorithme. Je ne sais pas où cela a été proposé ou mis en œuvre pour la première fois dans la littérature. Je serais intéressé d'entendre des références.

Voir par exemple Satisfy This: An Tentative to Solving Prime Factorization using Satisfiability Solvers de Stefan Schoenmackers et Anna Cavender qui le présente en détail. De plus, le défi DIMACS SAT à partir de la fin des années 90 avait des instances d'affacturage qui ont été générées par certains chercheurs, mais l'algorithme n'a peut-être pas été rédigé séparément dans un document à cette époque.

vzn
la source
1
fyi le lien papier est maintenant interdit 403
vzn
2
Concernant votre deuxième paragraphe: le théorème de Cook montre que tout problème dans NP peut être réduit à SAT.
Yuval Filmus
1
à droite, la preuve Cook est une preuve d'existence théorique générale et il existe des conversions / algorithmes plus directs / spécialisés souvent construits entre des problèmes NP complets (généralement avec une meilleure "surcharge"). faisait référence à ce dernier.
vzn
11

Juste pour être absolument clair, la factorisation entière n'est pas connue pour être NP-intermédiaire, simplement soupçonnée d'être basée sur le manque de preuve de complétude NP ou d'algorithme en temps polynomial (malgré beaucoup de travail mis dans les deux). Je ne connais aucun problème naturel (c'est-à-dire non construit par Ladner pour la preuve) qui soit définitivement NP-intermédiaire si P et NP sont différents.

D'accord, après cette exclusion de responsabilité, l' isomorphisme graphique est un autre candidat probable pour un problème NP-intermédiaire naturel. Il y a une simple réduction du temps polynomial de celui-ci à l' isomorphisme de sous -graphique - laissez simplement les graphiques les mêmes! L'isomorphisme graphique n'est que le cas particulier de l'isomorphisme sous-graphique où les deux graphiques ont la même taille. La touche finale est que l'isomorphisme sous-graphique est NP-complet.

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

Luke Mathieson
la source