Rucksackproblem - NP-komplett trotz dynamischer Programmierlösung?

Rucksackprobleme lassen sich leicht durch dynamische Programmierung lösen. Dynamische Programmierung läuft in Polynomialzeit; deshalb machen wir das, richtig?

Ich habe gelesen, dass es sich tatsächlich um ein NP-vollständiges Problem handelt, was bedeuten würde, dass das Lösen des Problems in einem Polynomproblem wahrscheinlich unmöglich ist.

Wo ist mein Fehler?

complexity-theory np-complete dynamic-programming Strin
quelle

Beachten Sie, dass DP in der "Tabellengröße" polynomisch ist. Die Tabelle ist für Knapsack exponentiell groß (siehe Kavehs Antwort).

Raphael

Antworten:

Das Rucksackproblem ist wenn die Zahlen als Binärzahlen angegeben werden. In diesem Fall benötigt die dynamische Programmierung exponentiell viele Schritte (in Bezug auf die Größe der Eingabe, dh die Anzahl der Bits in der Eingabe), um zu beenden . $\sf{NP\text{-}complete}$ $\dagger$

Wenn die Zahlen in der Eingabe dagegen unär sind, funktioniert die dynamische Programmierung in Polynomzeit (in der Größe der Eingabe).

Diese Art von Problemen wird als schwach $\sf{NP\text{-}complete}$ .

$\dagger$ : Ein weiteres gutes Beispiel, um die Bedeutung der für die Eingabe verwendeten Codierung zu verstehen, besteht darin, die üblichen Algorithmen zu berücksichtigen, um festzustellen, ob es sich bei einer Zahl um eine Primzahl handelt, die von bis zu und zu prüfen, ob eine davon teilt . Dies ist ein Polynom in aber nicht unbedingt in der Eingabegröße. Wenn binär angegeben ist, ist die Eingabegröße und der Algorithmus läuft in der Zeit die in der Eingabegröße exponentiell ist. Die übliche Komplexität der Berechnung eines Problems hängt von der Größe der Eingabe ab. $2$ $\sqrt{n}$ $n$ $n$ $n$ $\lg n$ $O(\sqrt{n}) = O(2^{\lg n/2})$

Diese Art von Algorithmus, dh Polynom in der größten Zahl, die Teil der Eingabe ist, aber Exponential in der Eingabelänge, wird Pseudo-Polynom genannt .

Kaveh
quelle

Aber denken Sie an die Gegenstände, die in den Rucksack gelegt werden sollen. Die Objekte müssen eingegeben werden, und eine solche Eingabe muss mit der Anzahl der Objekte polynomisch sein. Wenn viele Objekte vorhanden sind, ist die Eingabe mit der Größe des Problems polynomisch. Warum kann ich nicht sagen, dass das Knapsack-Problem ein P-Problem in Bezug auf die Tabellengröße ist? Liege ich falsch?

Strin

@Strin, nein, eine kleine Anzahl von Objekten kann ausreichen, um einen großen Rucksack zu fühlen. Wenn z. B. die Größe des Rucksacks , ist ein Objekt der Größe ausreichend. Die Größe der Eingabe ist ungefähr , viel kleiner als . (Ich gehe davon aus, dass wir über 0-1 Knapsack sprechen.)

m

$m$

m

$m$

2 \lg m

$2\lg m$

m

$m$

Kaveh

Können Sie die Eingabe in kleinere Eingaben aufteilen, deren Binärcodierung eine Größe hat, die den Algorithmus in Polynomialzeit beendet, und dann die Lösungen kombinieren?

Char

@Kaveh "Die Größe der Eingabe ist ungefähr 2 lg m" Ich verstehe nicht, woher Sie diesen Teil bekommen. Die Beziehung zwischen m(Packungsgröße) und n(Anzahl der Artikel) ist völlig unbekannt, oder? Und bezüglich "wenn die Zahlen als Binärzahlen angegeben werden" ... aber kannst du das nicht für irgendetwas sagen? Bei den meisten Algorithmen wird die Eingabegröße in Basis 10 angegeben. Warum wird hier von Binärdaten gesprochen? Und ob Sie binär, oktal, dezimal usw. codieren, actualhängt direkt von nund ab, wie oft Sie Ihre Hauptalgorithmusschleife durchlaufen W.

The111

@ The111, ich denke es ist besser wenn du das als neue Frage postest und ich werde eine Antwort posten. Ich denke, Ihre Frage ist grundlegender und es gibt Kommentare zu dieser Frage nicht sehr verwandt.

Kaveh

Die Hauptverwirrung liegt in der Differenz zwischen " Größe " und " Wert ".

" Polynomial Time " impliziert ein Polynom bezüglich der Größe der Eingabe.

" Pseudopolynomial Time " impliziert ein Polynom bezogen auf den Wert der Eingabe. Es kann gezeigt werden (siehe unten), dass dies äquivalent zu einer Exponentialfunktion für die Größe der Eingabe ist.

Mit anderen Worten: Es sei die Größe der Eingabe und Wert der Wert der Eingabe. $N_{size}$ $N_{val}$

Polynomialzeit: für $O(N_{size}^x)$ $x\in\mathbb{N}$

Pseudopol. Zeit: für $O(N_{val}^x)$ $x\in\mathbb{N}$

Das Rucksackproblem hat nun eine pseudopolynomielle und keine polynomielle Lösung, da die dynamische Programmierlösung eine Laufzeit , die von einem Wert abhängt - dh , wobei ein Wert ist, der die maximale Kapazität darstellt. $O(nW)$ $W$

Jetzt kann ein Wert in eine Größe umgewandelt werden, indem er in der Anzahl der Stellen dargestellt wird, die für die Darstellung erforderlich sind. gibt an, wie viele Stellen erforderlich sind, um mit Basis darzustellen . Dies kann gelöst werden, ergibt: $N_{size}=Log_b(N_{val})$ $N_{val}$ $b$ $N_{val}$

N_{v a l} = b^{N_{s i z e}}

$N_{val}=b^{N_{size}}$

Das Einfügen in die pseudopolynomiale Zeitdefinition zeigt, dass es exponentiell in : $N_{size}$

Pseudopol. Zeit: für $O(b^{xN_{size}})$ $b, x\in\mathbb{N}$

bcorso
quelle

Ich habe hier ein Konto erstellt, um mich zu bedanken! Erst nach deinem Beispiel habe ich es endlich verstanden.

Inoryy

Ihre Antwort schlägt alle, Bravo!

Muhammad Razib

Um diese großartige Antwort zu ergänzen, können wir sagen, dass, wenn wir das W von 100 auf 101 ändern, die Größe des Problems nicht erhöht wird, die Größe erhöht wird, wenn wir ein weiteres Bit zu W hinzufügen, wodurch es doppelt so groß wird, also würde die Tabelle Wenn Sie doppelt so viele Zeilen haben und die Größe um eins erhöhen, verdoppelt sich die Problemzeit, weshalb sie exponentiell ist.

Amen

@bcorso Angenommen, Sie haben den Wert N erhalten. Und Sie mussten die Summe der Zahlen von 1 bis N ermitteln und die for-Schleifenmethode verwenden. Das wäre ein pseudopolynomieller Zeitalgorithmus.

DollarAkshay

Das in Karps Artikel definierte Knapsack-Problem ist NP-Complete, da es eine Reduzierung von anderen NPC-Problemen (in diesem Fall Exact Cover) auf Knapsack gibt. Dies bedeutet, dass es keinen Polynomalgorithmus gibt, der alle Instanzen des Knapsack-Problems lösen kann , es sei denn, . $\text{P}=\text{NP}$

Es gibt jedoch verschiedene Varianten (z. B. 0-1 Knapsack und andere ), die möglicherweise polynomzeitliche Lösungen oder gute Approximationen aufweisen oder nicht. Dies ist jedoch nicht dasselbe wie das allgemeine Knapsack-Problem. Es kann auch effiziente Algorithmen geben, die für bestimmte (Familien von) Instanzen funktionieren , aber diese Algorithmen werden für andere Instanzen länger dauern.

Ran G.
quelle