Warum ist lineare Programmierung in P aber ganzzahlige Programmierung NP-schwer?

35

Die lineare Programmierung (LP) ist in P und die ganzzahlige Programmierung (IP) ist NP-hart. Da Computer jedoch nur Zahlen mit endlicher Genauigkeit manipulieren können, verwendet ein Computer in der Praxis Ganzzahlen für die lineare Programmierung. Sollte LP und IP aus diesem Grund nicht in derselben Komplexitätsklasse liegen?

complexity-theory polynomial-time Sasha die Noob
quelle
7
Ein wenig zu jmites Antwort hinzufügen: Es gibt viele Fälle, in denen Integritätsbeschränkungen das Problem sehr viel schwieriger machen. Zum Beispiel kann das Fractional-Knapsack-Problem in Polynom-Zeit gelöst werden, obwohl das Integer-Knapsack-Problem NP-Hard ist. Dies gilt also nicht nur für LP und IP.
user340082710
7
Selbst wenn wir davon ausgehen, dass Computer Operationen mit ganzen Zahlen ausführen, bedeutet dies nicht, dass die zurückgegebene Lösung eine ganze Zahl ist. es kann rational sein, dh das Verhältnis zweier ganzer Zahlen. Und das gibt viel mehr Flexibilität. Und natürlich können wir eine rationale Lösung nicht immer in eine praktikable Lösung für das geistige Eigentum umwandeln . Im Allgemeinen unterliegt das IP mehr Einschränkungen für die Variablen, als nur nach einer integralen Lösung zu fragen. Stellen Sie sich ein Integer-Programm vor. 0,1
Mega
1
Es ist nicht so schwer, Zahlen mit unendlicher Präzision zu manipulieren, wenn Sie wollen, besonders wenn sie rational sind. Endliche Präzision ist lediglich eine Optimierung zur Verkürzung der Laufzeiten.
2
@Hurkyl "Es ist nicht so schwer, Zahlen mit unendlicher Präzision zu manipulieren, wenn man will, besonders wenn sie rational sind." Es gibt eine strenge Teilmenge der reellen Zahlen, die als berechenbare Zahlen bezeichnet werden. Diese enthält Rationalen + Zahlen wie sqrt (2) usw. und ist als die Menge von Zahlen definiert, die von einer Turing-Maschine berechnet werden können. Diejenigen, die dort nicht enthalten sind, können per Definition nicht von einem Computer manipuliert werden.
Sasha the Noob
1
@SashatheNoob Was du sagst, steht nicht im Widerspruch zu dem, was Hurkyl gesagt hat. Für berechenbare Zahlen gibt es keine vordefinierte Höchstgrenze für die Genauigkeit (sie können beliebig eingestellt werden, vorausgesetzt, die Turing-Maschine verfügt über genügend Speicher - daher ist die Genauigkeit unbegrenzt). Um zu sagen, dass die Teilmenge der berechenbaren Zahlen alle rationalen Zahlen enthält, geben Sie zu, dass Computer Zahlen mit unendlicher Präzision manipulieren können. (Hurkyls Aussage ist absolut richtig. Die Tatsache, dass die Genauigkeit für bestimmte Datentypen begrenzt ist, ist lediglich eine Optimierung.)
BrainSlugs83

Antworten:

9

Ich kann nicht kommentieren, da es 50 Wiederholungen erfordert, aber es gibt einige Missverständnisse, die verbreitet werden, insbesondere Raphaels Kommentar "Im Allgemeinen bedeutet eine kontinuierliche Domäne, dass es keine rohe Gewalt gibt (und keine klugen Heuristiken, um sie zu beschleunigen)."

Das ist absolut falsch. Der entscheidende Punkt ist in der Tat die Konvexität. Abgesehen von einigen technischen Einschränkungen ist das Minimieren einer konvexen Funktion (oder das Maximieren einer konkaven Funktion) über eine konvexe Menge im Sinne einer polynomiellen Zeitkonvergenz im Wesentlichen trivial.

Man könnte sagen, dass die Konvexität eines Problems in der "mathematischen" Optimierung mit der Realisierbarkeit gieriger Algorithmen in der "Informatik" -Optimierung übereinstimmt. Dies ist in dem Sinne, dass beide lokale Suchmethoden ermöglichen. Sie müssen in einem gierigen Algorithmus niemals einen Back-Track ausführen, und Sie müssen niemals eine Abstiegsrichtung in einem konvexen Optimierungsproblem bereuen. Lokale Verbesserungen der Zielfunktion werden Sie IMMER näher an das globale Optimum bringen.

Dies ist im nicht konvexen Fall nicht der Fall. Hier mag es ein globales Minimum geben, aber es gibt mehrere lokale Minima, auf die ein lokaler Abstiegsalgorithmus immer angewendet wird, genau wie bei gierigen Algorithmen bei NP-Problemen. Manchmal finden sie das wahre Optimum, meistens nicht.

Benjamin Lindqvist
quelle
23

Die kurze Antwort: Weil Sie mit Ganzzahlen Boolesche Werte für SAT simulieren können , aber wenn Sie sich nicht darauf beschränken, können Sie SAT nicht wirklich simulieren. Sie erhalten eine realisierbare Antwort, die jedoch keine Bedeutung mehr für die SAT-Instanz hat, die Sie simulieren wollten.

P≠NP

jmite
quelle
21

Der Grund, warum die lineare Programmierung "effizient" ist, besteht darin, dass der Lösungsraum durch ein einziges konvexes Polyeder dargestellt werden kann. Wenn man versucht, den "höchsten" Scheitelpunkt auf diesem Polyeder zu finden (man kann eine lineare Transformation auf jedes lineare Programmierproblem anwenden, damit "Höhe" der zu maximierenden Größe entspricht), dann kann man von jedem Scheitelpunkt entlang der Kanten nach wandern der höchste Punkt, ohne jemals "bergab" fahren zu müssen. Was die Ganzzahlprogrammierung "schwierig" macht, ist, dass es keinen zusammenhängenden Lösungsraum gibt, sondern viele nicht zusammenhängende Lösungsräume und keine Möglichkeit, schrittweise auf die optimale Lösung hinzuarbeiten.

Superkatze
quelle
2
Das Schlüsselwort hier ist "Konvexität"
Cody
1
Handelt es sich bei diesem Hügel nicht um eine Simplexmethode, von der keine Variante im schlimmsten Fall als polynomisch bekannt ist?
Jbapple
1
Es gibt viele Probleme, die in diskreten Räumen (die diskrete Suchen ermöglichen) einfacher zu lösen sind als im kontinuierlichen Raum.
Raphael
@Raphael: Kannst du einige Beispiele für solche Probleme nennen? Ich habe darüber nachgedacht und kann mir nicht viele einfallen lassen.
Cody
@cody Finden von Maxima / Minima von (eindimensionalen) Funktionen. Sehen Sie sich hier ein hübsches Beispiel an, das erst zugänglich wird, wenn festgestellt wird, dass wir den endlichen Suchraum auf einen endlichen reduzieren können. Beachten Sie, dass LPs auf diese Weise etwas Besonderes sind: Wenn wir feststellen, dass wir nur die Ecken eines Polyeders berücksichtigen müssen, erhalten wir einen endlichen Suchraum. Im Allgemeinen bedeutet eine kontinuierliche Domäne, dass es keine rohe Gewalt gibt (und keine klugen Heuristiken, um sie zu beschleunigen).
Raphael
3

Die anderen Antworten sind richtig, aber ich finde sie ein bisschen technisch. Angenommen, Sie haben eine Matrix gefegt (eliminiert) und suchen nach einer Lösung. Die Matrix sieht dann so aus:

column x1 x2 x3 x4 x5 x6 | solution
-----------------------------------
       1           1  1  | 3
          1              | 1
             1     1     | 2
                2  1  1  | 1

Q.

Albert Hendriks
quelle