Everyone should be excited. At long last someone has solved a P NP problem. It could alter the dynamic of the computer industry. Moreover, these linear algorithms may represent valuable intellectual property. But what is P NP? P versus NP has been a problem in computer science for many years. It poses a question whether every problem whose solution can be efficiently checked by a computer can also be efficiently solved by a computer. It was introduced in 1971 by Stephen Cook in his paper "The complexity of theorem proving procedures". It is considered the most important unsolved problem in the computer industry. Everyone in the computer industry is interested in the problem. However, no one has come close to a solution, or even a partial solution for any P NP problem. It is one of the most elusive and complex problems in the history of the computer industry.
Since over 45 years have passed many terms have been used to describe the problem. Additionally, there are numerous descriptions of the problem that are perhaps causing as much confusion as clarification. Specifically, what is P; what is NP; and what does NP complete mean? Moreover, what does the word “efficiently” mean in terms of computer programming? Likewise, presented are many extrapolated time descriptions that are not necessarily applicable to every P NP problem. For this assessment only polynomial and exponential time are needed. This documentation describes the problem with a specific P NP dilemma. Then it demonstrates linear algorithms to solve this problem.
The P NP problem can be restated as the following question: Suppose that a solution to a problem can be computed quickly. Then, can all the solutions also be computed quickly? Again there is an adverbial term “quickly”. The definition of quickly used here represent algorithms that run in polynomial time. But what is polynomial time? The word polynomial means an algebraic expression consisting of one or more summed terms, each term consisting of a constant multiplier and one or more variables raised to integral powers. Its applicability to P NP is in finding an algorithm or set of algorithms that are linear, opposed to exponential in design. An exponent is a number or symbol placed to the right of and above another number, symbol, or expression, denoting the number of times that number, symbol, or expression is to be multiplied by itself. For sake of clarity think of polynomial time as a linear algorithm. Then think of exponential time as an algorithm that raises each successive occurrence of a logic loop or a process of summation to a power. All other types of mathematical time extrapolations are not applicable to understanding this P NP solution.
Often examples are used to help understand the problem. Let us use the example of a set of six integers (2, 3, 7, 14, -15,10) looking for a subset of integers that sum to zero. A subset (2 + 3 -15 + 10) sums to zero and is contained within the set of six integers. For sake of argument let us equate this to the P aspect of the P NP problem. Specifically, is it possible to find at least one subset within a set of integers that sums to zero? If so, this will satisfy the P aspect of the P NP problem. Likewise let us equate the NP aspect of the problem as finding all the subsets that sum to zero. To better understand the complexity of finding NP subsets take a look at this set of six integers (1, 1, 1, -1, -1, -1). For this set of six integers there are 19 subsets that sum to zero. This set of eight integers (1, 1, 1, -1, -1, -1, 2, -2) has 51 subsets that sum to zero, with this set of eight integers (1, 1, 1, 1, -1, -1, -1 -1) having 69 subsets that sum to zero. As the number of integers increase the ability to find all subsets that sum to zero also increases in complexity.
The following example represents the application of an exponential solution applied to this P NP problem using a set of six single digit integers. Let these letters represent symbolic integer variables (A) (B) (C) (D) (E) (F) where (A) can be a positive integer from 1 to 9 or a negative integer from -1 to -9. Refer to the table below with columns of all possible values.
A B C D E F
(1, -1) (1, -1) (1, -1) (1, -1) (1, -1) (1, -1)
(2, -2) (2, -2) (2, -2) (2, -2) (2, -2) (2, -2)
(3, -3) (3, -3) (3, -3) (3, -3) (3, -3) (3, -3)
(4, -4) (4, -4) (4, -4) (4, -4) (4, -4) (4, -4)
(5, -5) (5, -5) (5, -5) (5, -5) (5, -5) (5, -5)
(6, -6) (6, -6) (6, -6) (6, -6) (6, -6) (6, -6)
(7, -7) (7, -7) (7, -7) (7, -7) (7, -7) (7, -7)
(8, -8) (8, -8) (8, -8) (8, -8) (8, -8) (8, -8)
(9, -9) (9, -9) (9, -9) (9, -9) (9, -9) (9, -9)
Column A has 18 possible values, likewise for columns B through F. An exponential solution could take the value in column A and then add it to every possible occurrence of the value in column B and then check it for an answer or resulting variable X equal to zero.
A B
1 + 1 = X
1 + 2 = X
1 + 3 = X
...
1 + -7 = X
1 + -8 = X
1 + -9 = X
then
2 + 1 = X
2 + 2 = X
2 + 3 = X
...
2 + -7 = X
2 + -8 = X
2 + -9 = X
also
-1 + 1 = X
-1 + 2 = X
-1 + 3 = X
and
-1 + -1 = X
-1 + -2 = X
-1 + -3 = X
This yields 18 X 18 (or 18 squared) for the number of possible subsets. Therefore 324 possible equations exist. However, only 18 subsets satisfy the anticipated result of zero, that being (1 + -1, 2 + -2, 3 + -3 ... ; -1 + 1, -2 + 2, -3 + 3), and so forth. So 324 possible equations must be computed to find the one or ones that sum to zero. Note this is for single digit integers and only for columns A and B. A similar process is necessary for all other two-digit column combinations. Now if column C is added to the process with another 18 possible values it becomes more complex. For example:
A B C
1 + 1 + 1 = X
1 + 1 + 2 = X
1 + 1 + 3 = X
...
1 + 2 + 1 = X
1 + 2 + 2 = X
1 + 2 + 3 = X
...
1 + -9 + -7 = X
1 + -9 + -8 = X
1 + -9 + -9 = X
then
2 + 1 + 1 = X
2 + 1 + 2 = X
2 + 1 + 3 = X
...
2 + 2 + 1 = X
2 + 2 + 2 = X
2 + 2 + 3 = X
...
2 + -9 + -7 = X
2 + -9 + -8 = X
2 + -9 + -9 = X
This yields 18 X 18 X 18 (or 18 cubed) for the number of possible subsets. For sets of three integers 5,832 equations need to be checked to see if any sum to zero. Starting with columns A, B and C, a similar process is needed for all other combinations summing three columns. The same applies with four, five and six integer sets.
Two Integer Sets
A+B, A+C, A+D, A+E, A+F
B+C, B+D, B+E, B+F
C+D, C+E, C+F
D+E, D+F
E+F
For each set of two integers, there are 324 (18X18) equations that need to be evaluated. So for two integer sets there are 4860 (324 X 15) equations that need to be evaluated.
Three Integer Sets
A+B+C, A+B+D, A+B+E, A+B+F, A+C+D, A+C+E, A+C+F, A+D+E, A+D+F, A+E+F
B+C+D, B+C+E, B+C+F, B+D+E, B+D+F, B+E+F
C+D+E, C+D+F, C+E+F
D+E+F
For each set of three integers, there are 5832 (18X18X18) equations that need to be evaluated. So for three integer sets there are 116,640 (5832 X 20) equations that need to be evaluated.
Four Integer Sets
A+B+C+D, A+B+C+E, A+B+C+F, A+B+D+E, A+B+D+F, A+B+E+F , A+C+D+E, A+C+D+F, A+C+E+F, A+D+E+F
B+C+D+E, B+C+D+F, B+C+E+F, B+D+E+F
C+D+E+F
For each set of four integers, there are 104,976 (18X18X18X18) equations that need to be evaluated. So for four integer sets there are 1,574,640 (104,976 X 15) equations that need to be evaluated.
Five Integer Sets
A+B+C+D+E, A+B+C+D+F, A+B+D+E+F, A+B+C+E+F, A+C+D+E+F, B+C+D+E+F
For each set of five integers, there are 1,889,568 (18X18X18X18X18) equations that need to be evaluated. So for five integer sets there are 11,337,408 (1,889,568 X 6) equations that need to be evaluated.
Six Integer Set
A+B+C+D+E+F
For a six integer set 34,012,224 (18X18X18X18X18X18) equations need to be evaluated.
Therefore, for a set of six single digit integers a total of 47,045,772 (4860+116,640+1,574,640+11,337,408+34,012,224) equations need to be evaluated. The conclusion being that this exponential solution is neither efficient or quick.
Extrapolating this example for two digit integers opposed to one digit integers suggests an increasing amount of processing time on a computer. It also suggests that P does not equal NP and also indicates that finding an NP complete solution would require an inordinate amount of equations to be evaluated. Extrapolating this leads to the assumption that an NP complete solution might be impossible for a set of twenty-five two digit integers.
Until now no one has designed any solution in polynomial time. This means that no one has designed a linear algorithm to solve this problem. This is true even with the example of six, single digit, integers. To solve this problem a set of algorithms are needed that do not require exponential processing or logic. As such provided are examples of linear algorithms for two, three and four integer subsets for a set of six integers.
01 02
01 03
01 04
01 05
01 06
02 03
02 04
02 05
02 06
03 04
03 05
03 06
04 05
04 06
05 06
These numbers represent (in computer jargon) indexes or subscripts. They are not concerned with the values of the integers. They view them instead as a table of symbolic occurrences. Think of them like place holders pointing to the position of a number in a sequence of integers. Therefore, using these algorithms, the following process of computation could take place. Specifically, the example of (2, 3, 7, 14, -15, 10) the (01 02) would sum 2 + 3, the (01 03) would sum 2 + 7, the (02 06) would sum 3 + 10, and the (05 06) would sum -15 + 10. For this subscripting algorithm there are 15 equations that need to be evaluated. Of course none of these equations sum to zero. Adding to this technique and algorithm design it will be necessary to process a “threes” algorithm. That is to say it will need to evaluate sets of integers that contain three values. That algorithm is provided next.
01 02 03
01 02 04
01 02 05
01 02 06
01 03 04
01 03 05
01 03 06
01 04 05
01 04 06
01 05 06
02 03 04
02 03 05
02 03 06
02 04 05
02 04 06
02 05 06
03 04 05
03 04 06
03 05 06
04 05 06
Taking the example of (2, 3, 7, 14, -15, 10) the (01 02 03) would sum 2 + 3 + 7, the (02 04 06) would sum 3 + 14 + 10, the (04 05 06) would sum 14 + -15 + 10. For this algorithm 20 equations are evaluated. Still none of them when added together equal zero. Further adding to the design of these algorithms, next is the subscripting algorithm for four integers, specifically looking for four integers that sum to zero.
01 02 03 04
01 02 03 05
01 02 03 06
01 02 04 05
01 02 04 06
01 02 05 06
01 03 04 05
01 03 04 06
01 03 05 06
01 04 05 06
02 03 04 05
02 03 04 06
02 03 05 06
02 04 05 06
03 04 05 06
Again taking the example of (2, 3, 7, 14, -15, 10) the (01 02 03 04) would sum 2 + 3 + 7 + 14, and so forth. In looking at the set of six integers the subset of (2 + 3 + -15 +10) is noted. Specifically the subscripting set of (01 02 05 06) sums to zero. Therefore, to find an equation that sums to zero 41 equations need to be evaluated. In this example P would equate to 41 as well as NP. Specifically, 41 equations need to be evaluated to determine P and 41 equations need to be evaluated to determine NP. However, if it is not known if there are more that sum to zero the remaining equations need to be evaluated. This is needed to determine “NP Complete”. Therefore, extrapolating the design, the five member subset algorithm is provided and looks like this.
01 02 03 04 05
01 02 03 04 06
01 02 03 05 06
01 02 04 05 06
01 03 04 05 06
02 03 04 05 06
With six members there is only one summing process that includes every integer in the set and it would look like this.
01 02 03 04 05 06
Merging these five subscripting algorithms it is possible to find every equation that sums to zero. The remarkable thing about the design of these algorithms is that only 57 equations need to be evaluated. These five subscripting algorithms could then be combined into a composite called the #6 algorithm. In short, the nomenclature for the algorithms is indicative of the number of members in the set to be evaluated. Therefore, the #2 algorithm would only have a few entries and the #25 algorithm would have a significant number of entries, consisting of a composite of 24 sub algorithms. Nevertheless, from one to another the design of the algorithms is identical. Note the value of the integers are independent of the algorithms. They work as symbolic variables accessed by a subscript. With this technique it is possible to find every equation that sums to zero, both quickly, and efficiently. Contrast these linear algorithms with those of any exponential method, the difference is significant. Specifically 47,045,772 equations need to be evaluated using the exponential example whereas with the linear algorithms only 57 need to be evaluated.
So then does P = NP? Almost always P does not equal NP. Oddly it depends on the values of the integers in the set. When there is only one solution P = NP, that is when using polynomial time as the common comparison value. Nevertheless, this assumes a priori knowledge of the solution, specifically knowing when NP is actually NP complete. Otherwise, if there is more than one solution, NP always takes a greater amount of polynomial time. Therefore, for sets of integers with multiple subsets summing to zero P never equals NP.
The applicability of these algorithms to solve other P NP problems is open for debate. However, software has been developed to demonstrate proof of concept. Comparing the results in polynomial time of these two types of logic processes provide insight into the value of the linear algorithms, as well as the pitfalls of all existing exponential designs.