Teilmengen-Summe, pseudo-polynomielle zeitdynamische Programmierlösung?

8

Ich habe vor einiger Zeit das P vs NP-Problem gefunden und kürzlich an dem Teilmengen-Summenproblem gearbeitet. Ich habe einen Wikipedia-Artikel über das Subset Sum-Problem sowie die Frage Subset Sum Algorithm gelesen

Ich habe mir das Problem angesehen und einige Lösungen gefunden, aber bisher scheinen sie NP zu sein. Ich glaube, ich kann in NP-Zeit einen ausreichend schnellen Algorithmus erstellen.

Mein Problem ist, dass ich theoretisch nicht gut bin, daher hilft es mir nicht viel, über das Cook-Levin-Theorem oder nicht deterministische Turing-Maschinen zu sprechen.

Was ich möchte, ist eine Erklärung der Teilmenge der pseudopolynomialen zeitdynamischen Programmiermenge, die auf Wikipedia angegeben ist.

Ich habe es gelesen und glaube, ich verstehe das allgemeine Konzept, warum es NP anstelle von P ist (bezogen auf die Größe der Eingabe und nicht auf die Operationen damit), aber ich verstehe den Algorithmus nicht.

Ich würde mich freuen, wenn jemand ein Beispiel mit einigen Zahlen geben würde und wie es funktioniert. Es würde mir sehr helfen, weil es:

  • Gib mir Ideen, um meinen zukünftigen Algorithmus zu verbessern
  • Helfen Sie mir intuitiv zu verstehen, wenn ein Algorithmus pseudo-polyonmial anstelle von NP ist.
algorithms dynamic-programming Gemeinschaft
quelle
1
crab.rutgers.edu/~guyk/ex/part.pdf
Robert Harvey
1
cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/…
Robert Harvey
2
Was ist die Frage? Anfangs dachte ich, Sie fragen nach einem Beispiel, wie der Algorithmus, mit dem Sie verknüpfen, funktioniert, aber ich bin dem Link gefolgt und es gibt dort bereits ein Beispiel.
Rgrig
2
Ich habe auch Probleme, die Beiträge zu verstehen, es ist nicht klar, was gefragt wird. Übrigens ist jedes Problem in P auch in NP. Ich denke, Sie meinen NP-vollständig anstelle von NP an mehreren Stellen in Ihrem Beitrag. Schließlich ist es nicht sinnvoll zu sagen, dass sich ein Algorithmus in NP befindet. NP ist eine Klasse von Sprachen, keine Algorithmen. Ich vermute, dass Sie das verbreitete Missverständnis haben, dass NP einen Algorithmus für nichtpolynomielle Zeit (oder exponentielle Zeit) bedeutet.
Kaveh
2
Wenn Sie die Größe der Werte in der Eingabe begrenzt haben (die Anzahl der Bits für jeden Wert logarithmisch in der Gesamtzahl der Bits der Eingabe gebunden haben), kann das Problem mithilfe der dynamischen Programmierung in Polynomzeit gelöst werden. Wenn sie nicht begrenzt sind, können sie Werte haben, die exponentiell groß sind, und die Größe der Tabelle für die dynamische Programmierung wäre exponentiell.
Kaveh

Antworten:

5

Umformulierung von Kavehs Kommentar als Antwort:

Wenn Sie die Größe der Werte in der Eingabe begrenzt haben (die Anzahl der Bits für jeden Wert logarithmisch in der Gesamtzahl der Bits der Eingabe gebunden haben), kann das Problem mithilfe der dynamischen Programmierung in Polynomzeit gelöst werden. Wenn sie nicht begrenzt sind, können sie Werte haben, die exponentiell groß sind, und die Größe der Tabelle für die dynamische Programmierung wäre exponentiell.

jmite
quelle