Ich versuche zu beweisen, dass P = NP ist, indem ich einen Algorithmus entwickle, der ein NP-komplettes Problem in polynomieller Zeit löst. Das NP-vollständige Problem, das ich ausgewählt habe, ist das Subset-Summen-Problem. Das Subset-Sum-Problem ist das einfachste NP-vollständige Problem, das ich kenne, und ich halte die Dinge gerne einfach. {Der Leser kann die Artikel von Wikipedia.org über “P vs NP” und das “Subset-Sum Problem” als eine vorläufige Einführung in dieses Thema wählen}

Das Teilmengen-Summen-Problem lautet wie folgt: Ist bei einer endlichen Menge C von ganzen Zahlen ungleich Null jede Teilmenge von C in der Summe genau Null? Es folgen zwei Beispiele:

(Beispiel 1) Sei die Menge A = (-25, 63, -12, 44, 88, -69, -11, 13, -66, 37)

Teilmenge-Summe(A) = Ja, weil (-25, -69, 13, 37, 44) eine Teilmenge von A ist, und

-25+-69+13+37+44=0

(Beispiel 2) Sei die Menge B = (-2, -4, -6, 5, 9, 11)

Teilmengen-Summe(B) = Nein, weil keine der 63 nicht-leeren Teilmengen von B Elemente hat, die sich genau zu Null summieren.

Die Anzahl der Ganzzahlen in der Menge ist die Eingangsgröße (N). Beispiel 1 hat eine Eingabegröße von 10. In Beispiel 2 ist N=6.

Wenn Subset-Sum(X) = Ja ist, wird jede Teilmenge von X, deren Elemente sich genau zu 0 summieren, als Zertifikat bezeichnet. In Beispiel 1 ist also (-25, -69, 13, 37, 44) ein Zertifikat, das Subset-Sum(A) = Ja zeigt. In Beispiel 2 hat B keine Zertifikate, denn Subset-Sum(B) = Nein. Jede Menge (X), für die Subset-Sum(X) = Ja ist, hat mindestens ein Zertifikat.

Die einzigen bekannten Methoden, dieses Problem zu lösen, beinhalten die eine oder andere Art von erschöpfender Suche. Mit anderen Worten: Selbst der beste bekannte Algorithmus zum Lösen von Subset-Sum(C) ist kaum besser, als jede Teilmenge von C zu summieren und das Ergebnis mit 0 zu vergleichen.

Auf der Suche nach einem schnelleren Algorithmus zum Lösen des Teilmengen-Summen-Problems erstellen wir eine Variation des Teilmengen-Summen-Problems (nennen wir es das “Teilmengen-Summen-Variation-Problem” oder das “SSV-Problem”), so dass:

Wenn A eine endliche Menge von ganzen Zahlen ungleich Null ist und B eine ganze Zahl ist,

SSV(A, B) = Ja, wenn es eine Teilmenge von A gibt, deren Elemente sich genau zu B summieren, und SSV(A, B) = Nein, wenn nicht.

Es sollte darauf hingewiesen werden, dass, wenn B auf Null gesetzt wird, man SSV(A, 0) erhält, was genau dasselbe ist wie Subset-Sum(A). Da Subset-Sum ein bekanntes NP-vollständiges Problem ist und gezeigt werden kann, dass es eine Instanz des SSV-Problems ist, können wir schlussfolgern, dass das SSV-Problem ebenfalls NP-vollständig ist (weil jeder Algorithmus, der alle Instanzen des SSV-Problems lösen kann, auch in der Lage sein muss, alle Instanzen des Subset-Sum-Problems zu lösen).

Lassen Sie uns nun eine Variation des SSV-Problems erstellen, die nur eine endliche, nicht leere Menge A der natürlichen Zahlen akzeptiert, und nennen Sie es das “Natural-Subset-Sum-Variation Problem” oder “NSSV-Problem”. Dieses neue Problem ist zwar nicht NP-komplett, wird sich aber später als sehr nützlich für uns erweisen. Um NSSV(A, B) zu lösen, habe ich den in Abbildung 1 gezeigten Algorithmus entwickelt (der Algorithmus selbst ist nicht wichtig. Die Tatsache, dass er NSSV(A, B) in Polynomialzeit löst, ist der Punkt). Für den Fall, dass die Abbildung unklar ist, kann eine andere Version unter http://www.myfilestash.com/userfiles/contactm3/illustration%201.JPG gefunden werden.

Kehren wir nun zum ursprünglichen Subset-Sum-Problem zurück. Erinnern Sie sich, dass jede ‘ja’-Instanz von Subset-Sum(C) (mindestens) ein Zertifikat hat, das eine Teilmenge von C ist, die sich zu Null summiert. Beachten Sie, dass, da alle Zertifikate aus einer nicht leeren Menge von Nicht-Null-Ganzzahlen bestehen, die sich zu Null summieren, ein Zertifikat mindestens eine positive Ganzzahl und mindestens eine negative Ganzzahl haben muss. Beachten Sie auch, dass die Summe aller positiven ganzen Zahlen eines Zertifikats gleich dem absoluten Wert der Summe aller negativen ganzen Zahlen eines Zertifikats ist (deshalb summiert sich die Menge zu Null). Diesen Wert, die Summe aller positiven ganzen Zahlen eines Zertifikats, werde ich als “Zertifikatswert” bezeichnen.

Eine Lösung für P VS. NP Algorithmen?
Eine Lösung für P VS. NP Algorithmen?

In Beispiel 1 ist (-25, -69, 13, 37, 44) ein Zertifikat für Subset-Sum(A) = Ja. Die Summe der positiven Elemente dieses Zertifikats ist 13 + 37 + 44 = 94. Der Absolutwert der Summe aller negativen Elemente ist |-25 + -69| = |-94| = 94. Somit ist der Zertifikatswert von (-25, -69, 13, 37, 44) 94.

Jedes Zertifikat hat (natürlich) einen Zertifikatswert, und dieser Zertifikatswert muss eine natürliche Zahl sein (weil er eine positive, von Null verschiedene ganze Zahl ist).

Der Zertifikatswert eines Zertifikats, das Subset-Sum(C)=Yes zeigt, wird niemals größer sein als entweder die Summe aller positiven ganzen Zahlen in C oder der absolute Wert der Summe aller negativen ganzen Zahlen in C, je nachdem, welcher Wert kleiner ist. Das liegt daran, dass ein Zertifikatswert gleich der Summe aller positiven ganzen Zahlen in einem Zertifikat ist (und auch dem absoluten Wert der Summe aller negativen ganzen Zahlen im Zertifikat), also nicht größer sein kann als die Summe aller positiven ganzen Zahlen der übergeordneten Menge (C) (und auch nicht größer als der absolute Wert der Summe aller negativen Elemente in der übergeordneten Menge).

Nennen wir also die Summe aller positiven Elemente in C (oder den absoluten Wert der Summe aller negativen Elemente in C, je nachdem, welcher Wert kleiner ist) den maximalen Zertifikatswert der Menge (C), und stellen wir ihn durch das Symbol m dar. (Ich kann auch zeigen, dass ein minimaler Zertifikatswert für C existiert, aber das ist im Hinblick auf die vorliegende Aufgabe nicht notwendig).

Wir können schlussfolgern, dass jedes Zertifikat, das Subset-Sum(C) = Ja zeigt, einen Zertifikatswert hat, der eine natürliche Zahl von 1 bis m ist. Jetzt machen wir einen Fortschritt!

Es sei die Menge aller positiven Elemente von C = p, und die Menge aller Absolutwerte aller negativen Elemente von C = n.

Ich weiß, dass, wenn Subset-Sum(C)=Yes, dann gibt es (mindestens) ein Zertifikat, das dies beweist, und es muss einen Zertifikatswert von 1 bis m haben. Ich weiß auch, dass dieser Zertifikatswert die Summe aller Elemente einer Teilmenge von p ist, und auch eine Teilmenge von n.

Um festzustellen, ob ein Zertifikat für Teilmenge-Summe(C)=Ja existiert (und somit festzustellen, ob Teilmenge-Summe(C)=Ja), prüfen wir zunächst, ob es eine Teilmenge von p gibt, die einen beliebigen Wert von 1 bis m ergibt. Da p nur Elemente enthalten kann, die natürliche Zahlen sind, haben wir es mit einer Reihe von Standard-NSSV-Problemen der Form NSSV(p, B) zu tun, wobei B ein Wert von 1 bis m ist. Wenn für NSSV(p, B) keine “Ja”-Instanz gefunden wird, nachdem alle Werte von B von 1 bis m geprüft wurden, dann gibt es keine Teilmenge von p, die sich zu einem Wert summiert, der ein Zertifikatswert sein könnte, also gibt es kein Zertifikat, das Subset-Sum(C)=Ja zeigt, also Subset-Sum(C)=Nein. Wenn eine “Ja”-Instanz für NSSV(p, B) auftritt, prüfen wir sofort, ob NSSV(n, B)=”Ja” für denselben Wert von B. Wenn ja, zeigt dies, dass es eine Teilmenge von n und eine Teilmenge von p gibt, die beide denselben Wert ergeben, was auf Subset-Sum(C)=Ja hinweist.

Um diesen Algorithmus grafisch zu demonstrieren, habe ich das Flussdiagramm in Abbildung 2 erstellt. Für den Fall, dass die Abbildung unübersichtlich wird, finden Sie eine weitere Version unter http://www.myfilestash.com/userfiles/contactm3/illustration%202.JPG Dieser Algorithmus ist so konzipiert, dass er versucht, ein Zertifikat aus den Elementen der übergeordneten Menge “aufzubauen”, anstatt eine erschöpfende Suche aller möglichen Teilmengen dieser Elemente zu versuchen. Dieser Algorithmus stützt sich auf meinen ersten Algorithmus, um höchstens 2m NSSV-Probleme in Polynomialzeit zu lösen, was zu einer erschöpfenden Suche aller möglichen Zertifikatswerte anstelle aller Teilmengen der übergeordneten Menge führt. Da sich das Subset-Summen-Problem als NP-vollständig erwiesen hat und mit diesem Algorithmus in Polynomialzeit gelöst werden kann, befindet sich das Subset-Summen-Problem in der Komplexitätsklasse NP-vollständig, sowie in der Komplexitätsklasse P. Daher ist P = NP.