To address the problem "Does P = NP?" we try to find the most difficult problems in NP - these are surely the best candidates for problems that in NP but not in P - and by the same token, if we can prove that the most difficult problems in NP are also in P, then P = NP.

But how can we identify the hardest problems in NP?  Our measure of problem difficulty so far has been the computational complexity of the best algorithm for solving the problem ... but for the problems we are interested in, we have no idea what the best algorithm is.  We are in the uncomfortable position of trying to compare the difficulty of problems that we don't know how to solve.

Well, it turns out we can do this in a rather clever way.  We imagine two problems X and Y.  We would like to show that X is "easier" than Y (or, more precisely, that X is "no harder" than Y).  We do this indirectly by showing that IF we could find an efficient algorithm for Y, this would immediately give us an efficient algorithm for X.

To show this relationship between X and Y, we demonstrate that any instance of X (i.e. any specific set of values or objects that X applies to) can be transformed in polynomial time into an instance of Y (i.e. a specific set of values or objects that Y applies to) in an answer-preserving way.  That is, if the answer to X on that specific set of values is YES, then the answer to Y on the transformed set of values is also YES (and similarly for NO).

Here's a simple example:  

X:  Given a set of n integers, are there more positive than negative integers in the set?        (NB:  X is a decision problem, and it is in NP)

Y:  Given a set of n integers, is the sum of the set positive?        (Y is also a decision problem, and Y is also in NP)

It is important to note that both of these problems are so simple that we can immediately see good algorithms for solving them.  Ignore that for the moment - we are focusing on the relationship between the problems.

Suppose we are given an instance of X (a specific set of integers), and suppose we have no idea how to solve it.  We ask "If I knew how to solve Y, how could I use that knowledge to solve X?"   Solving X requires counting, but solving Y involves adding ... the key insight is that counting is equivalent to adding 1's.  So if we transform the instance of X into an instance of Y by replacing every positive integer by 1, and every negative integer by -1, then solving Y on the transformed set will give us a YES answer if and only if the answer to X on the original set is YES.  So our transformation is answer-preserving, as required ... but is it a polynomial-time transformation?  Yes, it is, because all we need to do is make a single, constant-time change to each element of the set - the entire transformation requires O(n) time.

Our terminology for this kind of transformation is reduction.  We say X reduces to Y.  This is confusing to a lot of people, because an intuitive interpretation of the word "reduce" often suggests "simplify".  Here, the reduction goes from the "easier" problem (X) to the "harder" problem (Y).  It is useful to remind ourselves exactly what we mean by X reduces to Y:  if we could solve Y, then we could also solve X.

Reduction is NOT about:
    - showing that there is an algorithm for Y
    - showing that there is an algorithm for X
    - showing that X is difficult or easy
    - showing that Y is difficult or easy

Reduction IS about:
    - showing that IF we could solve Y in polynomial, then we could also solve X in polynomial time by transforming instances of X into instances of Y.


The next step in the argument is to observe that reduction is transitive.  If X reduces to Y, and Y reduces to Z, then X reduces to Z - the transformation now takes two steps, but it is still polynomial-time.

Now we can imagine long chains of problems, linked by reduction.  The first problems in each chain would be quite easy, and as we move along the chains the problems get harder and harder.  The problems we are searching for, the most difficult problems in NP, will be at the far ends of the chains.

Finally, we get back to Cook and Levin.  To describe their amazing discovery, we need one more definition.

CNF-SAT:  CNF-SAT is a problem in NP, defined as follows:  Let E be a Boolean expression with m clauses and n literals (literals = variables, possibly negated), in which
    - each clause contains only "OR" connectives
    - the only connectives between clauses are "AND"s
CNF-SAT asks "Is there a way to assign True and False to the literals so that E is True?"

Clearly CNF-SAT is in NP - if the answer is YES and we are told which literals should be True and which should be False, verifying the answer is easy: we just make sure there is at least one True literal in each clause of E.

And now, at last, the jewel in the crown:

The Cook-Levin Theorem:
    Let X be any problem in NP.  Then X reduces to CNF-SAT.


The truly staggering implications of this theorem .... will be discussed in class on Monday.