Teilmengen-Summenproblem ist NP-vollständig?

Wenn ich es richtig weiß, ist das Teilmengenproblem NP-vollständig. Hier haben Sie ein Array von n ganzen Zahlen und Sie erhalten eine Zielsumme t. Sie müssen die Zahlen aus dem Array zurückgeben, die sich zum Ziel summieren können (falls möglich).

Aber kann dieses Problem nicht in Polynomzeit durch eine dynamische Programmiermethode gelöst werden, bei der wir eine Tabelle n X t erstellen und Fälle wie die letzte Zahl annehmen, die sicher in der Ausgabe enthalten ist, und dann wird das Ziel t- a [n]. In einem anderen Fall ist die letzte Zahl nicht enthalten, dann bleibt das Ziel gleich t, ​​aber das Array wird von der Größe n-1. Auf diese Weise reduzieren wir die Größe des Problems weiter.

Wenn dieser Ansatz korrekt ist, ist dann nicht die Komplexität dieses Polynoms n * t? und wenn dies zu P gehört und auch NP-vollständig ist (nach dem, was ich höre), dann ist P = NP.

Sicher fehlt mir hier etwas. Wo ist die Lücke in dieser Argumentation?

Vielen Dank,

Ihre Logik ist korrekt - und was Sie beschrieben haben, ist ein gültiger Teilmengen-Summen-Algorithmus, der sie löst O(nt).

Diese Art von Algorithmus ist jedoch pseudopolynomisch , was bedeutet, dass er exponentiell zur Anzahl der Bits ist, die zur Darstellung der Eingabe verwendet werden. Das heißt, wenn Sie t1000 sind, kann ich Ihr Programm 10-mal langsamer machen, indem ich eine weitere 0 hinzufüge ( tist jetzt 10000).

Während der Algorithmus zum Wert von nund polynomisch ist t, ist er exponentiell zur Größe der Eingabe (Anzahl der Zeichen, Bits, wie auch immer Sie sie nennen möchten, in der Eingabe).

Und daher liegt dieses Problem nicht in P (es sei denn, P = NP oder ähnliches).

Quelle und weiterführende Literatur