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?
np-complete
reductions
factoring
Nathan Jordan
quelle
quelle
Antworten:
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.
quelle
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!).
quelle