Ultra Fast Sum Subset Algorithm P v/s NP by Oscar Riveros
P vs. NP
The fifth problem we describe comes from theoretical computer science and is easy to state: is P = NP?Compared to the previous ones, the explanation of what this problem asks is much simpler, although the answer so far seems as hard to be obtained as in the previous cases. Here, P and NP denote classes of problems that ask for a "yes-or-no" answer. Informally, asking if P=NP is the same as asking if for every yes-or-no problem for which the answer is easy to check (an NP problem) it is true that the answer is also easy to determine (a P problem). Obviously, every P problem is a NP problem, but it is not known if the NP class is a stricly larger class of problems than the P class. If somebody would prove that P=NP or find an NP problem that is not P, he or she would get a million dollars. The solution would have major consequences not only in computer science, but also in other mathematical disciplines and in biology and cryptography. For example, the safety of currently used cryptosystems in economic and internet transactions depends on not knowing a polynomial time algorithm to break the code. If P=NP were proven by a constructive method, it would mean that the current cryptosystems would lose their safety and would have to be replaced.
To make it a little bit more precise, we have to say what is meant by "easy" in the statement above: it means relatively fast in the sense that the number of the steps in the algorithm for getting the answer is not too large. The official term for this "fastness" ispolynomial time. An algorithm is said to be polynomial time if the number of steps it performs, i.e. its running time, is upper bound by a polynomial depending only on the algorithm itself and the size of the input. For example, all basic arithmetic operations can be done in polynomial time.
Examples of problems that are NP, but not known if they are also P, include the following:
- The subset sum problem: given a set of integers, does the sum of some non-empty subset equal exactly zero? For a chosen subset it is easy to check if the sum of its elements is zero, but to find such a set can be very difficult and it is not known if there is a polynomial time algorithm for the solution.
- The party problem: Say you want to organize a wedding and plan to invite many of your 500 aquantances, but the largest hall the restaurant can offer has only 100 places. Since you cannot invite them all, you consider their mutual relations and notice that there are some that won't come if you invite somebody else from the list. The problem is to decide how to fill as many of the places on your wedding feast without inviting any two incompatible guests. If you take a concrete guest list of 100 of them, it is easy to check if there are any two incompatible members of the list. But, it is not easy (no polynomial time algorithm is known for this) to find a list satisfying the condition.