Reading

These notes and Unit 6 sections 3 and 4.

Quiz questions

None.

Review quiz problem

We know NP, but what do "N" and "P" stand for?

From last class we have a formal definition of the class NP. However, we still don't know where the name comes from, i.e. what do N and P stand for? [Hint: it does not stand for "Not Polynomial"!] "NP" stands for "Nondeterministic Polynomial Time", meaning the class of problems that can be solved in polynomial time on a nondeterministic machine. That's all well and good, but what is a "nondeterministic" machine?

Nondeterministic Machines/Programs

Here's what I think is a nice analogy for nondeterministic computation: There's a movie called "Sliding Doors" in which this character played by Gwenyth Paltrow rushes to catch a subway train. It's a very near thing as to whether she'll get in on time or not, and at the precise last instant the movie branches off into two "alternate realities" - one in which she catches the train and one in which she doesn't. For the rest of the movie, these two alternate realities unfold simultaneously. This is like nondeterministic computing.

If your program asks for a random bit of data, the subsequent computation will depend on whether a 1 or a 0 was returned. However, you'll get one or the other, and the program will proceed with a single computation based on that value. In nondeterministic computation you can request a "nondeterministic bit" and, instead of getting one or the other, the computation branches off into two alternate realities, or "alternate computations", which proceed simultaneously - one branch corresponding getting a 1 and the other corresponding to getting a 0. If you have several of these "nondeterministic bits" in your program, you'll have many "alternate reality computations" proceeding simultaneously. That's nondeterministic computing.

Great, but in the end we need one single answer out of these many simultaneous "alternate reality" computations. What'll it be? Well, recall that we've been restricting ourselves to decision problems in our discussions of P and NP. For nondeterministic computation, we need to do the same thing. So, assuming we're trying to solve a decision problem, if each alternate computation comes up with the result "false", then the result of the nondeterministic computation is "false". As long as at least one of the alternate computations comes up with the result "true" the result of the nondeterministic computation is "true".

Real computers, like the one I'm typing on right now, are deterministic not nondeterministic. The nondeterministic model of computing is not supposed to model real computers, they are supposed to help categorize certain kinds of computations. However, there is this idea of a "quantum computer" out there, and quantum computers may be able to compute like our nondeterministic machines. This kind of "both at once" idea is present in quantum mechanics - Schroedinger's Cat, for example - and is the real basis for quantum computing. However, it's not clear that there will ever be general purpose programmable quantum computers. Still, the possiblity is out there ...

So how does this characterization of NP as the class of problems that can be solved in polynomial time with a nondeterministic machine mesh with our definition of NP as the class of decision problems for which we have certificates that can be verified in polynomial time? Well, suppose I have a definition of certificates for instances of Problem A and a polynomial time algorithm for verifying certificates. Then I could generate a string of nondeterministic bits as long as any certificate, and run the verification algorithm using that sequence of bits as the certificate. Thus, I would effectively be simultaneously verifying all possible certificates. One of them will give me TRUE as an answer if and only if the answer to the original instance is TRUE.

P vs NP

Now we know what P and NP are. It's clear that if you can solve a problem in polynomial time on a deterministic machine you can solve it in polynomial time on a nondeterministic machine - just don't use the nondeterministic capabilities - so we know that P ⊆ NP. However, is it true that any problem that can be solved in polynomial time on a nondeterministic machine can be solved in polynomial time on a deterministic machine? in which case we would have P = NP. Well ... I don't know. If you can either prove or disprove P = NP, however, tell me. There are people who are willing to give a lot of money to anyone who can answer this question. Notice that the "P = NP" problem is first on this list of problems for which the Clay Institute will give $1,000,000 to the solver. They have a nice one paragraph description of P vs NP, and a nice article tying the Minesweeper game to "P vs NP".

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.

Reducibility

A common way to solve a new problem is to reduce it to an old problem - typically an old problem we know how to solve. For example, in class we talked about how we could reduce the problem of finding the median value in an array to the problem of sorting an array. The idea is that solving an instance of the new problem boils down to solving an instance of the old problem. With decision problems, the idea of "reducing" can be made quite precise.

The decision Problem B is reducible to the decision Problem A if there is an 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 Instance B is true if and only if the answer to Instance A is true.

Example of equivalent problem Instances
Problem A - Set Partition: Given positive integer weights w1, ..., wn, Can the weights be partitioned into two sets of equal weight?
Problem B - Simple Knapsack: Given positive integer weights w1, ..., wn and capacity C, Does some subset of the weights sum to exactly C?
Instance of B
w1w2w3 w4w5 w6C
32765920
---- Reduce to ----> Equivalent Instance of A
w1w2w3 w4w5 w6w7
3276598
Instance of B
w1w2w3 w4w5 w6C
3276 5920
<-- Solutions to Both --> Equivalent Instance of A
w1w2w3 w4w5 w6w7
327 6598

Polynomial Time Reducibility

To investigate the P = NP question we'll be interested in situations in which this "reducing" can be done in polynomial time. 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.

Time vs. Space

Suppose we know that Algoritm X runs in polynomial time? What can we infer from this? Well, oddly enough, we can infer that the problem can be solved using an amount of memory that's polynomial in the input size! This probably seems a bit odd: We know something about the time required to solve this problem, and we somehow infer something about the space required to solve the problem. Well, consider this analogy:
	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.

Polynomial time reduction of Simple Knapsack to Set Partition

Here is a straightforward algorithm that takes an instance of the Simple Knapsack problem and returns an equivalent instance of the Set Partition problem:

Input: Simple Knapsack problem w1, w2, ..., wn and capacity C
Output: A Set Partition problem that's equivalent to the input Knapsack Problem.

  1. set S = w1 + w2 + ... + wn
  2. if (C >= S/2) set wn+1 = 2*C - S
    else set wn+1 = S - 2*C
  3. return Set Partition problem w1, w2, ..., wn, wn+1

We should prove that the given 0/1 Knapsack problem and the Set Partition problem produced by our algorithm are equivalent.
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!