Sind alle Integer Linear Programming Probleme NP-Hard?

10

Soweit ich weiß , liegt das Zuweisungsproblem in P, da der ungarische Algorithmus es in Polynomzeit lösen kann - O (n 3 ). Ich verstehe auch, dass das Zuweisungsproblem ein ganzzahliges lineares Programmierproblem ist, aber die Wikipedia-Seite gibt an, dass dies NP-Hard ist. Für mich bedeutet dies, dass das Zuweisungsproblem in NP-Hard liegt.

Aber sicherlich kann das Zuweisungsproblem nicht sowohl bei P als auch bei NP-Hard liegen, sonst wäre P gleich NP? Bedeutet die Wikipedia-Seite einfach, dass der allgemeine Algorithmus zur Lösung aller ILP-Probleme NP-Hard ist? Einige andere Quellen geben an, dass ILP NP-hart ist, was mein Verständnis von Komplexitätsklassen im Allgemeinen wirklich verwirrt.

Matt
quelle
4
NP-hart bedeutet, dass (es sei denn, P = NP) jeder deterministische Algorithmus für die Polytime bei einigen (unendlichen) Instanzen fehlschlägt . Normalerweise gibt es auch eine Reihe einfacher Instanzen.
Sasho Nikolov
1
Beachten Sie, dass die Aussage nicht "jede IP ist NP-hart" lautet, sondern " jede IP zu lösen ist NP-hart".
Raphael
1
Als Bemerkung ist IP für feste Dimension in P.
A.Schulz

Antworten:

19

Wenn ein Problem NP-schwer ist, bedeutet dies, dass es eine Klasse von Instanzen dieses Problems gibt, die NP-schwer sind. Es ist durchaus möglich, dass andere spezifische Klassen von Instanzen in Polynomzeit lösbar sind.

Betrachten Sie zum Beispiel das Problem, eine 3-Färbung eines Graphen zu finden . Es ist ein bekanntes NP-Hard-Problem. Stellen Sie sich nun vor, dass seine Instanzen auf Diagramme beschränkt sind, bei denen es sich beispielsweise um Bäume handelt. Es ist klar, dass Sie in Polynomzeit leicht eine 3-Färbung eines Baumes finden können (tatsächlich können Sie auch eine 2-Färbung finden).

Betrachten Sie Entscheidungsprobleme für eine Sekunde. Ein Verfahren zum Nachweis der Härte eines Entscheidungsproblems besteht darin, eine Polynomreduktion (Karp) aus einem anderen Problem , von dem bekannt ist, dass es NP-hart ist. In dieser Reduktion zeigen Sie, dass es eine Funktion , die jede Instanz des Problems einer Instanz des Problems so zuordnet, dass: eine Ja-Instanz für eine Ja-Instanz für . Dies impliziert, dass das Lösen von "mindestens so schwierig" sein muss wie das Lösen von selbst.Q f q Q P q Q.PQfqQPqP f ( q ) qQf(q)Pf(q)q

Beachten Sie, dass es nicht erforderlich ist, dass das Bild von gleich der Menge der Instanzen von . Daher ist es durchaus möglich, dass Problem das auf eine Teilmenge von Instanzen beschränkt ist, nicht schwer ist.P P.fPP

Um zu Ihrer ursprünglichen Frage zurückzukehren:

  • Das Zuweisungsproblem kann in Polynomzeit gelöst werden, dh eine Lösung für jede Instanz des Zuweisungsproblems kann in Polynomzeit berechnet werden.
  • ILP ist NP-schwer: Im Allgemeinen kann es schwierig sein, eine Lösung für ein ILP-Problem zu berechnen, dh es gibt Fälle von ILP, die schwierig sind.
  • Einige spezifische Fälle von ILP können in Polynomzeit gelöst werden.
Steven
quelle
Könnten Sie bitte erklären, ob es notwendig ist, dass jede Instanz von abbildet ? wir nicht eine Teilmenge von abbilden ? dh muss das Vorbild von ganz ? Q Q f Q.fQQfQ
Mat
Es ist nicht erforderlich, dass jede Instanz von abbildet, solange es eine (unendliche) Klasse von harten Instanzen von abbildet . Um beispielsweise zu zeigen, dass NP-hart ist, kann eine Reduzierung des auf planare Graphen beschränkten 3-Farben-Problems bereitgestellt werden. Q Q P.fQQP
Steven
13

Nein, Sonderfälle können einfacher sein.

Betrachten Sie diese IP beispielsweise mit für :ai0i[1..n]

mini=1nxiai

st und für .i=1nxi1
 xiNi[1..n]

Es findet das Minimum unter (das, für das in einer optimalen Lösung zwangsläufig ). Das Finden des Miniums von Zahlen ist eindeutig ein Polynomproblem.a1,,anxi=1n

Raphael
quelle
0

Sie können ein polynomiell lösbares Problem als IP modellieren. Dies bedeutet nicht, dass das Problem NP-schwer ist. Es bedeutet einfach, dass kein Polynomalgorithmus zur Lösung des IP-Modells Ihres Problems bekannt ist (es sei denn, P = NP).

Wie Sie vorgeschlagen haben, liegt das Zuweisungsproblem in P, aber Ihr IP-Modell ist NP-hart.

Austen
quelle
3
Die IP in Raphaels Antwort kann in Polynomzeit gelöst werden. Mit anderen Worten, im Allgemeinen kennen wir keinen schnellen Algorithmus zum Lösen von IPs, aber es gibt spezielle Fälle von IP-Problemen, für die wir schnelle Algorithmen haben.
Juho
0

Nein, es gibt eine spezielle Art von ganzzahligem Programm. Wenn die Beschränkungsmatrix TUM (völlig unimodulare Matrix) ist, kann sie in das lineare Programm entspannt werden, das in Polynomzeit gelöst werden kann.

Jianhao Ma
quelle
-4

Das Zuweisungsproblem ist kein ILP, sondern ein LP-Problem und daher nicht NP-schwer.

Julia
quelle
4
Ich bin mir nicht sicher, warum Sie denken, dass das Zuweisungsproblem kein ILP ist. Es kommt also vor, dass in diesem Fall die optimale Lösung für das lineare Programm auch die optimale Lösung für das ganzzahlige lineare Programm ist ... aber das bedeutet nicht, dass es keine Instanz von ILP ist.
DW
Außerdem sind einzelne Instanzen für sich genommen niemals NP-hart. Sie möchten sagen, "dies ist eigentlich eine einfache Instanz", aber das ist eine viel kompliziertere Aussage (definieren Sie "einfach").
Raphael