This question of whether there are problems in NP that cannot be solved in polynomial time is the biggest open problem in computer science and one of the biggest in math as well. Truth of the matter is, most of us are pretty convinced that P ≠ NP, even though we can't prove it.
The decision Problem B is reducible to the decision Problem A if there is an algorithm that transforms instance IBof problem A into an instance IB of problem B that is equivalent. In this context, "equivalent" means that the answer to Instance A is true if and only if the answer to Instance B is true.
Problem A - Set Partition: Given positive integer weights w1, ..., wn, Can the weights be partitioned into two sets of equal weight? | |||||||||||||||||||||||||||||||
Problem B - 0/1 Knapsack: Given positive integer weights w1, ..., wn and capacity C, Does some subset of the weights sum to exactly C? | |||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||
|
The decision Problem B is reducible to the decision Problem A if there is a polynomial time algorithm that transforms instance IBof problem B into an instance IA of problem A that is equivalent. In this context, "equivalent" means that the answer to IA is true if and only if the answer to IB is true.
Here's why polynomial time redicibility is such a big deal:Suppose Problem B is polynomial time reducible to problem A. If there is a polynomial time algorithm for solving A, then we have a polynomial time algorithm for solving B. Here it is:
IB ---------------------------> IA ---------------------------> solution Polynomial Polynomial Time Time Reduction Solution s = size IB time = O(sk) t = size IA time = O(tm) = O(sk) = O(O(sk)m) = O(skm)So we deduce that the time to solve IB is O(skm), which is polynomial in the size of IB. The only real mystery is why we were able to deduce that t = size IA = O(sk), and that is explained by the following.
Suppose that a program runs in 1/10 of a second, and the machine it runs on executes an instruction every 1/1,000,000 of a second. What's the most memory this program could possibly use? The most memory would be used if every instruction wrote to a new memory location. Since instructions reference at most a word at a time, this would use 1 word = 4 bytes per instruction. In 1/10 of a second, our machine performs 100,000 instructions, so we use at most 400,000 bytes, or 400K.So, you should see how information about runing time translates into information about space usage. We know now that Algorithm X requires only polynomial space, so any output from X will have bit-size that's polynomial in the input size.
Input: Simple Knapsack problem w1, w2,
..., wn and capacity C
Output: A Set Partition problem
that's equivalent to
the input Knapsack Problem.
Proposition: Given Simple Knapsack problem w1, w2, ..., wn and capacity C, the above algorithm returns an equivalent Set Partition problem.
Proof: Let S = w1 + w2 + ... + wn. First, we'll show that if the Knapsack problem is true, so is the set partition problem. Suppose that some subset of weights fills the knapsack to capacity C. The sum of all the wieghts not in the knapsack is S - C. If C ≥ S/2 the partition problem returned by the algorithm adds weight wn+1 = 2*C - S, so adding wn+1 to the set of weights not in the knapsack gives gives a set of total weight S - C + 2C - S = C, and we have a partition into two sets of weight C. If C < S/2 the partition problem returned by the algorithm adds weight wn+1 = S - 2*C, so adding wn+1 to the set of weights in the knapsack gives a set of total weight C + S - 2C = S - C, which is equal to the set of weights not in the knapsack. Thus if the original knapsack problem can be solved, so can the returned partition problem.Next we'll show that if the Partition Problem is true, so is the Knapsack problem. Suppose that the n+1 wieghts in the partition problem can be partitioned into two sets of equal weight. If C ≥ S/2 the partition problem returned by the algorithm adds weight wn+1 = 2*C - S, so the sum of all weights in the partition problem is S + 2C - S = 2C. Thus, both partition sets sum to C, and whichever doesn't have the weight wn+1 is a solution to the original knapsack problem. If C < S/2 the partition problem returned by the algorithm adds weight wn+1 = S - 2*C, so the sum of all weights in the partition problem is S + S - 2*C = 2*(S - C). Thus, both partition sets sum to S - C, and if we remove weight wn+1 from whichever set has it, the remaining weights sum to S - C - (S - 2*C) = C and thus provide a solution to the original knapsack problem. Thus if the returned partition problem can be solved, so can the original knapsack problem.
We can't have one problem solvable without the other one being solvable as well, so either both are solvable or neither are solvable. Thus the two problems are equivalent.
Clearly, our algorithm takes polynomial time. Thus, Simple Knapsack is polynomial time reducible to Set Partition, which means among other things that if we can solve Set Partition in polynomial time we can also solve Simple Knapsack in polynomial time. So there's another way to win your million dollars!