Hat jedes NP-Problem eine ILP-Formulierung in Polygröße?

14

Da die ganzzahlige lineare Programmierung NP-vollständig ist, gibt es eine Karp-Reduktion von jedem Problem in NP zu diesem. Ich dachte, dies impliziert, dass es für jedes Problem in NP immer eine ILP-Formulierung in Polynomgröße gibt.

Aber ich habe Artikel über bestimmte NP-Probleme gesehen, in denen Leute Dinge wie "Dies ist die erste Formulierung in Polygröße" oder "Es ist keine Formulierung in Polygröße bekannt" schreiben. Deshalb bin ich verwirrt.

complexity-theory np-complete reductions linear-programming Andy
quelle
8
Sie sollten ein Beispiel nennen oder ein vollständigeres Zitat machen;)
hugomg
1
Es gibt eine Polynomreduktion von jedem NP-vollständigen Problem zu jedem anderen NP-vollständigen Problem. Nur weil wir wissen, dass eines existiert, heißt das nicht, dass wir wissen, wie man es konstruiert.
Joe
3
@Joe, wir wissen, wie man ein Problem in NP auf 3-Sat reduziert, und auch jeder praktische NP-vollständige Problembeweis stammt aus einer Reihe von Reduktionen von 3-Sat, so dass Sie immer Reduktionen von einem bestimmten NPC-Problem zu erstellen können irgendein anderes.
Andy
10
@andy hast du deine Frage nicht einfach mit diesem Kommentar beantwortet? Sie wissen, dass jede NP-Probleminstanz als polysierte 3-SAT-Instanz geschrieben werden kann, und Sie wissen, dass eine 3-SAT-Instanz als polysierte ILP-Instanz geschrieben werden kann, und ein Polynom, das auf ein Polynom angewendet wird, ist ein anderes Polynom Erwarten Sie von einer Antwort?
Artem Kaznatcheev
2
Wenn jemand sagt, dass dies die erste Poly-Size-Formulierung ist, bedeutet dies, dass dies die erste Formulierung ist, die ausdrücklich angegeben wird . Die durch SAT erzielten Reduzierungen (auch wenn man sich um alle Details kümmert) sehen nicht gut aus und sind schwer zu handhaben. Wir wollen normalerweise Formulierungen, die natürlich und leicht zu verarbeiten sind.
Kaveh

Antworten:

5

Diese Antwort ist meist eine Zusammenfassung der Kommentare zu der obigen Frage.

Wenn ein Problem NP-vollständig ist, kann es mithilfe von Karps Reduktionen tatsächlich auf ILP reduziert werden (- Joe, andy). Behauptungen von "Formulierungen in Polynomgröße" von einem Problem zum anderen sind wahrscheinlich als direktere Formulierungen zu verstehen, im Gegensatz zu mehrfachen Reduktionen durch SAT (- Kaveh).

Realz Slaw
quelle
1

Ja. Jedes NP-Problem hat eine polynomgroße ILP-Formulierung.

Hier ist warum. Jedes NP-Problem hat eine polynomgroße Formulierung als Instanz von SAT. Darüber hinaus können alle üblichen Booleschen Operatoren - logisches ODER, logisches UND, logisches NICHT usw. - in ILP ausgedrückt werden, wobei eine konstante Anzahl von Variablen und Ungleichungen pro Booleschem Operator verwendet wird. Ausführliche Informationen dazu finden Sie unter Express-Boolesche Logikoperationen in ILP (Integer Linear Programming) . Auf diese Weise erhalten wir höchstens eine konstante Vergrößerung, wenn wir von SAT zu ILP wechseln. Dies impliziert, dass es eine polynomgroße Formulierung jedes NP-Problems als ILP-Problem gibt.

DW
quelle