Reduzieren des Ganzzahlfaktorisierungsproblems auf ein NP-Complete-Problem

17

Ich kämpfe darum, die Beziehung zwischen NP-Intermediate und NP-Complete zu verstehen. Ich weiß, dass, wenn P! = NP, basierend auf Ladners Theorem, eine Klasse von Sprachen in NP existiert, aber nicht in P oder in NP-Complete. Jedes Problem in NP kann auf ein NP-Complete-Problem reduziert werden. Ich habe jedoch keine Beispiele dafür gesehen, wie ein vermutetes NPI-Problem (wie die ganzzahlige Faktorisierung) in ein NP-Complete-Problem umgewandelt werden kann. Kennt jemand ein Beispiel für diese oder eine andere NPI-> NPC-Reduktion?

Nathan Jordan
quelle
4
Durch die Definition der NP-Vollständigkeit kann jedes Problem in NP auf jedes NP-vollständige Problem reduziert werden. Insbesondere zeigt Cooks Theorem, dass SAT NP-vollständig ist, und gibt Ihnen daher "explizit" eine solche Reduktion.
Yuval Filmus
1
@YuvalFilmus Ich verstehe, dass es eine Formalisierung gibt, dass eine solche Methode existiert. Ich habe jedoch nach einem konkreteren algorithmischen Ansatz gesucht, der der Reduktion des Hamilton-Zyklus-Problems auf das Traveling-Salesman-Problem ähnelt. Dabei können Sie alle Kantengewichte auf 1 setzen und TSP in der Grafik ausführen und prüfen, ob die zurückgelegte Strecke größer als | E | ist. Sowas nehme ich an.
Nathan Jordan

Antworten:

11

Zum Beispiel gibt es eine klassische Reduktion des Factorings auf SAT, was auch eine Quelle für vermutete "harte" SAT-Instanzen ist. Grundsätzlich verwendet man EE-Ideen zur binären Multiplikation, die in die SAT-Schaltung codiert sind. Stellen Sie sich die binäre Multiplikation als Addition einer Reihe von linksverschobenen Multiplikanden vor, die jeweils durch die Bits eines Multiplikators "maskiert" (UND-verknüpft) werden. Die Additionen können durch eine binäre Additionsschaltung ausgeführt werden, die eine Reihe von Volladdierern ist.

Ein talentierter Student könnte diesen Algorithmus entwickeln. Ich weiß nicht, wo es zuerst in der Literatur vorgeschlagen oder umgesetzt wurde. Ich würde mich über Referenzen freuen.

Siehe z. B. Satisfy This: Ein Versuch zur Lösung der Prime Factorization mithilfe von Satisfiability Solvers von Stefan Schoenmackers und Anna Cavender, in dem dies im Detail erläutert wird. Auch die DIMACS SAT-Herausforderung , die Ende der 90er Jahre begann, hatte Factoring-Instanzen, die von einigen Forschern generiert wurden, aber möglicherweise wurde der Algorithmus in dieser Ära nicht separat in einer Arbeit geschrieben.

vzn
quelle
1
fyi die Papierverbindung ist jetzt 403 verboten
vzn
2
Zu Ihrem zweiten Absatz: Cooks Theorem zeigt, dass jedes Problem in NP auf SAT reduziert werden kann.
Yuval Filmus
1
Richtig, der Cook-Beweis ist ein allgemeiner theoretischer Existenzbeweis und es gibt direktere / spezialisiertere Umwandlungen / Algorithmen, die häufig zwischen NP-vollständigen Problemen erstellt werden (normalerweise mit besserem "Overhead"). bezog sich auf Letzteres.
vzn
11

Um ganz klar zu sein, ist es nicht bekannt, dass die Ganzzahlfaktorisierung NP-intermediär ist. Es wird lediglich vermutet, dass der NP-Vollständigkeits- oder der Polynomialzeit-Algorithmus fehlen (trotz vieler Anstrengungen in beiden Bereichen). Ich kenne kein natürliches Problem (dh nicht von Ladner für den Beweis konstruiert), das definitiv NP-intermediär ist, wenn P und NP unterschiedlich sind.

Okay, nach diesem Haftungsausschluss ist der Graph-Isomorphismus ein weiterer wahrscheinlicher Kandidat für ein natürliches NP-intermediäres Problem. Es gibt eine einfache Reduzierung der Polynomzeit auf Subgraph Isomorphism - lassen Sie die Graphen einfach gleich! Der Graphisomorphismus ist nur der Spezialfall des Subgraphisomorphismus, bei dem beide Graphen die gleiche Größe haben. Der letzte Schliff ist , dass Subgraph Isomorphismus ist NP-vollständig.

Abgesehen davon gibt es natürlich immer die vom Cook-Levin-Theorem versprochene nicht so informative Reduktion. Wir wussten , dass jedes NP-Zwischenproblem eine nicht deterministische polynomzeitliche Turing-Maschine hat, die darüber entscheidet, und wir können dies in umwandeln eine Instanz von SAT (muss nur das TM erstellen!).

Luke Mathieson
quelle