I attempt to prove that P = NP by developing an algorithm that solves an NP-Complete problem in polynomial time. The NP-Complete problem I have chosen is the Subset-Sum Problem. The Subset-Sum Problem is the simplest NP-Complete problem I know of, and I like to keep things simple. {The reader may choose Wikipedia.org’s articles on “P vs NP” and the “Subset-Sum Problem” as a preliminary introduction to this topic}
The Subset-Sum Problem is this: Given a finite set, C, of non-zero integers, does any subset of C sum to exactly zero? Two examples follow:
(Example 1) Let the set A = (-25, 63, -12, 44, 88, -69, -11, 13, -66, 37)
Subset-Sum(A) = Yes, because (-25, -69, 13, 37, 44) is a subset of A, and
-25+-69+13+37+44=0
(Example 2) Let the set B = (-2, -4, -6, 5, 9, 11)
Subset-Sum(B) = No, because none of the 63 non-empty subsets of B have elements which sum to exactly zero.
The number of integers in the set is the input size (N). Example 1 has an input size of 10. In example 2, N=6.
When Subset-Sum(X) = yes, any subset of X who’s elements sum to exactly 0 is called a certificate. Thus, in example 1, (-25, -69, 13, 37, 44) is a certificate showing Subset-Sum(A) = Yes. In example 2, B has no certificates, for Subset-Sum(B) = No. Every set (X), such that Subset-Sum(X) = Yes, has at least one certificate.
The only known methods of solving this problem involve one kind of exhaustive search or another. In others words, even the best known algorithm for solving Subset-Sum(C) does little better than summing every subset of C and comparing the result to 0.
In search of finding a faster algorithm for solving the Subset-Sum Problem, let’s create a variation of the Subset-Sum Problem (call it the “Subset-Sum-Variation Problem” or the “SSV Problem”) so that:
When A is a finite set of non-zero integers, and B is an integer,
SSV(A, B) = Yes, if there exists a subset of A who’s elements sum to exactly B, and SSV(A, B) = No if not.
It ought to be pointed out that when B is set to zero, you get SSV(A, 0), which is precisely the same as Subset-Sum(A). Because Subset-Sum is a known NP-complete problem and can be shown to be an instance of the SSV Problem, we can conclude that the SSV Problem is also NP complete (because any algorithm that can solve all instances of the SSV Problem must also be able to solve all instances of the Subset-Sum Problem).
Now let’s create a variation of the SSV problem that will only accept a finite, non-empty set, A, of natural numbers, and call it the “Natural-Subset-Sum-Variation Problem” or “NSSV Problem.” This new problem, though not NP-Complete, will prove very useful to us later on. To solve NSSV(A, B), I developed the algorithm shown in illustration 1 (the algorithm itself is not important. The fact that it solves NSSV(A, B) in polynomial-time is the point). In case the illustration comes out unclear, another version can be found at http://www.myfilestash.com/userfiles/contactm3/illustration%201.JPG.
Now let’s come back to the original Subset-Sum Problem. Recall how every ‘yes’ instance of Subset-Sum(C) has (at least) one certificate, which is a subset of C which sums to zero. Note that, because all certificates are created by a non-empty set of non-zero integers that sum to zero, a certificate must have at least one positive integer, and at least one negative integer. Also note that the sum of all the positive integers of a certificate is the same as the absolute value of the sum of all negative integers of a certificate (that’s why the set sums to zero). This value, the sum of all the positive integers of a certificate, is what I will refer to as the “certificate-value”.
In Example 1, (-25, -69, 13, 37, 44) is a certificate for Subset-Sum(A) = Yes. The sum of its positive elements of this certificate is 13 + 37 + 44 = 94. The absolute value of the sum of all its negative elements is |-25 + -69| = |-94| = 94. Thus, (-25, -69, 13, 37, 44)’s certificate-value is 94.
Every certificate has a certificate-value (naturally), and this certificate value must be a natural number (because it is a positive, non-zero integer).
The certificate-value of a certificate showing Subset-Sum(C)=Yes will never be greater than either the sum of all the positive integers in C, or the absolute value of the sum of all the negative integers in C, whichever is lesser. This is because a certificate-value is equal to the sum of all positive integers in a certificate (and also the absolute value of the sum of all the negative integers in the certificate), thus cannot be larger than the sum of all positive integers of the parent set (C) (nor larger than the absolute value of the sum of all negative elements in the parent set).
So, let us call the sum of all positive elements in C (or the absolute value of the sum of all negative elements in C, whichever is lesser) the maximum certificate-value of the set (C), and let it be represented by the symbol m. (I can also show that a minimum certificate-value exists for C, but doing so is not necessary with regards to the task at hand).
We can conclude that any certificate that shows Subset-Sum(C) = Yes will have a certificate-value that is some natural number from 1 through m. Now we are making some progress!
Let the set of all positive elements of C = p, and the set of all the absolute values of all negative elements of C = n.
I know that if Subset-Sum(C)=Yes, then there is (at least) one certificate that proves as much, and it must have a certificate-value of from 1 through m. I also know that this certificate value is the sum of all the elements of some subset of p, and also some subset of n.
To determine whether a certificate exists for Subset-Sum(C)=Yes (and, thus, to determine whether Subset-Sum(C)=Yes) we begin by checking to see whether there is a subset of p that sums to any value from 1 to m. Since p can only contain elements that are natural numbers, we are faced with a series of standard NSSV problems in the form NSSV(p, B), where B is a value from 1 through m. If no “yes” instance is found for NSSV(p, B) after checking all values of B from 1 through m, then there is no subset of p that sums to any value that could possible be a certificate-value, thus there is no certificate showing Subset-Sum(C)=Yes, therefore Subset-Sum(C)=No. If a “yes” instance does occur for NSSV(p, B), we immediately check to see if NSSV(n, B)= “Yes” for the same value of B. If so, this shows there is a subset of n, and a subset of p, that both sum to the same value, thus indicating Subset-Sum(C)=Yes.
To demonstrate this algorithm graphically, I created the flow chart in illustration 2. In case the illustration comes out unclear, another version can be found at http://www.myfilestash.com/userfiles/contactm3/illustration%202.JPG
This algorithm is designed to try to “build” a certificate out of the elements in the parent set instead of trying an exhaustive search of all possible subsets of those elements. This algorithm relies upon my first algorithm to solve at most 2m NSSV problems in polynomial-time, thus resulting in an exhaustive search of all possible certificate-values instead of all subsets of the parent set. Since the Subset-Sum Problem has been shown to be NP-Complete and can be solved with this algorithm in polynomial-time, the Subset-Sum problem resides in complexity class NP-Complete, as well as complexity class P. Therefore, P = NP.
Recent Comments