Now it's time for the payload of the theory of NP completeness. We're going to
see some perfectly ordinary problems not apparently related to computation in
anyway, that are also NP complete. Of course we can cover only a tiny fraction
of the problems that are known to be NP complete. But the methods, ways of
designing reductions, are the things to take away from this discussion. If you
encounter a problem in your work, and can't come up with an efficient solution,
there is a good chance that you can devise a reduction that proves [inaudible]
complete. That proof guides your thinking. You need to consider for example, whether
you need to solve the problem in all its generality. Or whether a simple or special
case would give you what you need. You need to consider efficient algorithms that
offer an approximation to what you really want. Without the assurance of the problem
[inaudible] complete, you are less likely to want to attempt, or to justify to your
boss, taking one of these simplifying steps. But before moving onto reductions
that show the problem's node color and knapsack to be NP-complete, we introduce
one more nuance since the theory. Np-hard problems are those that would be
NP-complete if only they were an NP, but that are probably or certainly harder than
anything in NP. We talk about the tautology problem. Which is an example of
such as problem even though it is very closely related to the problem set. We are
ready to reduce three set to a number of other problems, thus showing each of them
meant be complete. These reductions can be directly from three set or from another
problem that we previously proved NP complete. Remember, the key issue is that
each reduction must be in polynomial time. However, in most cases, the construction
is computationally simple. So, as long as the output is of length polynomial in the
input, it will be easy to argue that the running time of the transducer, is
polynomial. Of course. If a problem is NP complete it must be an MP. Usually, this
part of the proof is quite simple, since a non-deterministic polytime Turing machine
can use its non-determinism to guess a solution in linear time. And then check
that it has guessed the solution using some polynomial amount of time. However,
there are some interesting cases where we can only show a problem to be NP hard.
Meaning that if it is in P, then P=NP. But the problem, itself, may or may not be an
NP. A curious example of an NP hard problem is the tautology problem. A
bullion expression is a totallogy if it true for every truth assignment. For
example, this expression is a totallogy. Every truth assignment makes X either true
or false so one of the first two terms, that is this or that, will have to be
true, and therefore the whole expression is true. We don't even need the term Y and
Z. If you look at Cook's original paper on NP completeness, he was really trying to
argue that totallogies required exponential time to recognize. Because
tautologies of the theorems of logic, that's what logicians care about, not
satisfiable expressions. Cook was able to reduce all of MP to satisfiability but
that is enough to show that if there were a poly-time algorithm for tautologies then
P equals MP. We'll address this point in a few slides. In fact, there is good reason
to believe the tautology problem is not an MP. On the other hand as compliment, the
non-tautologies. Including those inputs that don't make sense as Boolean
expressions, isn't np. We use the non-determinist to get [inaudible]
assignment, and evaluate the expression in polynomial in time for this truth
assignment. If the value is false, then the non-deterministic machine accepts its
input. On the other hand, the nondeterministic machine accepts whatever
it finds the value to be true. It accepts the satisfiable expressions, not the
[inaudible]. The class of languages called [inaudible] is those languages whose
complement is an [inaudible]. For example, we just argued that [inaudible] problem is
in [inaudible], because the non [inaudible] are an [inaudible]. P is
closing the complementation. We didn't prove this exactly, but it is easy to
show. Because if I have a deterministic touring machine that halts within P of N
steps for some polynomial P of N, we can modify it to accept the compliment
language. Just have the new machine sim, simulate the original. It halts without
accepting if the original machine accepts, and it goes to a new accepting state if
the original halts. Since the compliment of every language NP is also NP, just
surely an NP, that proves that class P is a subset of co-NP as well as an NP. And
another important connection is, that if p does equals n p, then p also equals co n
p. And, therefore, then n p and co n p are equal. However. It is possible, but
unlikely that MP and co-MP are the same, and both are bigger than NP. We can prove
the tautology problem to be for the proof. Suppose there is polytime algorithm for
the tautology problem, and given ebullient expression E, converted to (not) E, which
takes only linear time since all we have to do is add ?not' in a pair of
parentheses. Notice that E is satisfiable, if, and only if (not) E is not a
tautology. So use the hypothetical algorithm for the tautology problem to
tell whether or not, not E is tautology in polynomial time. Then just compliment the
answer. That is, say E isn't SAT whenever the answer you got is that not E is not a
tautology. And say E is not satisfiable whenever not E is found to be a tautology.
That would be a poly-time algorithm for sad which would show people's empty that
is all we need for proof that totalogy is empty heart. Now lets read a real problem
from operations research that Cobb proved to be NP complete. A node cover for a
graph is a set of nodes of that graph such that every edge has at least one of two
nodes in the set. We need to express the problem of finding a small as possible
node cover as a yes/no problem. We do so by asking what? They were given a graph G,
and an integer K. Does G have a node cover of size, K or less? This is the formal
problem or language called node cover. Notice that if we had a polytime algorithm
for the minimization problem. That is, given a graph, find a node cover of
smallest size. Then we could prove that the formal problem node cover was in P.
Just use the hypothetical polytime algorithm to find the smallest node cover.
Count the number of nodes in the cover and see if it is the nodes K. That means that
once we prove the formal node cover problem with s node version of the problem
to be n node complete. We also know there is also a node time polyalgorithm for the
minimization version unless p equals np. Here's an example of a graph. One of the
interesting things about NP complete problems and node cover is one such, Is
that even small instances of the problem seem hard, so how small a node cover can
we find to this graph, do you see the answer yet? We'll work it out. We have to
pick either c or d for our node cover. Or else, the edge c d isn't covered. We may
as well pick c, because c covers every edge that d covers and, and more. We also
have to pick either A or E, else the edge AE is not covered. But picking C and
either A or E does not cover the edge BF, so we need at least three nodes in the
cover. But here's one example that works, B, C and E together cover all the edges.
Thus, given this graph and the budget K=3, the answer is yes. The same answer applies
if the instance of no [inaudible] in this graph, this graph, with a higher budget.
However if we are given this graph with a budget of two or less the answer is no.
We're now going to prove a node cover to be NP complete, okay, we will give a
polytie reduction from three sat, given an instance of three sat, we construct a
graph. There is a node for each lit, literal of each clause. So the number of
nodes is three times the number of clauses. It helps to imagine the nodes
arranged in a rectangle. The columns corresponds to the clauses. Each column
has three nodes. One for each of its clauses. There are vertical edges
connecting each pair of nodes in a column and thus there are three vertical edges
per column. There are also horizontal edges that connect nodes in different
columns. Two nodes are connected if they represent literals with the same variable
and exactly one of those literals has that variable negated. And, finally, the budget
k is twice the number of clauses. Which is also exactly two-thirds of the nodes. So
here's an example of an instance of three set with four clauses. We'll construct the
graph that has a node cover of eight nodes, if and only if this expression is
satisfiable. So here's the column for the first clause. The literals of the first
clause are X, Y, and Z with no negations. So those are the labels of the three nodes
in this column. And similarly, we construct a column for each of the other
clauses. It is convenient that all four clauses have the same three variables in
order, either negated or not. So this graph is going to turn out to be easier to
understand than might be the case otherwise. Now I add the horizontal edges.
For example, in the top row, where all the X's are, each node labeled X is connected
to each node labeled not X. Again, because all the X nodes line up and the horizontal
edges are truly horizontal. In more complex examples, they would not be,
although they always go between columns. Similarly we see connections in the second
row between nodes Y and nodes not Y, and then the third row are the edges between Z
and not Z. And the final part of the output is the budget K, since there are
four clauses, the budget is K equals twice that or eight. The first thing to observe
about the constructive graph is that a node cover must have at least two of the
three nodes in every column. If it has only one note in the column then the
vertical edge between the two unselected notes will not be covered. Blanc But the
budget is exactly twice the number of clauses. So if all three nodes in one
column were in the node cover, then some other column will be short changed, it
could get only one node and we would not have a node cover. The conclusion is that
there can be no node cover with fewer than K nodes and that there is a node cover of
exactly K nodes, then these K nodes must be exactly two from each column. Were
going to show out there is a tight relationship between the node covers and
the truth assignments and this connection goes. Through the nodes that are not
selected for the node cover. That is, a satisfying assignment for the three-side
instance will yield a node-cover, if we omit from the node-cover one of the nodes
from each column that is made true by the assignment. And conversely, a node-cover
with two nodes per column will give us a satisfying assignment by making all the
literals [inaudible] nodes are uncovered to be true. We'll prove all this in a
minute, but first an example. For example, here's the three set instance we saw
earlier. And here's the graph of budget eight, that we constructed. Here's a truth
assignment. It happens to be a satisfying assignment so we can pick a node from each
column that is made true by the assignment. Here's one such choice. There
are others, for example, in the first column, we could have picked Y instead of
X. I claim that if we take the other two nodes from each column, we get a node
cover. Surely all the vertical edges are covered since we have two nodes in each
column, but what about the horizontal edges? Suppose we have a horizontal edge,
say with x at one end and not x at the other and neither end is in the node
cutter. That means both were selected as the literal that made their clause true.
But how could that be? They can't both be true in any one-truth assignment. So they
can't simultaneously make their clauses true. We need to show that what we
described is a polytime reduction from three [inaudible] to node cover. It is
easy to see the transducer takes polynomial time. It works clause-by-clause
generating no more nos than there are literals. The vertical edges can be
generated at the same time and they number only three per clause. The horizontal
edges can be generated easily if we list all the nodes labeled by each literal.
After seeing all the clauses we can generate horizontal edges for each
variable X. We look at the list of nodes for literals X and not X. We generate
edges for all pairs one from each list. The total number of edges generated is no
more than quadratic in the length of the input and the edges can be generated in
constant time each. We also need to show the reduction is correct of course. That
is, if we construct graph G and budget. K for the three-side expression E. Then g
has a node cover of size k or less, if and only if e is satisfiable. For one
direction. Suppose he is satisfiable and let A be a satisfying truth assignment.
The argument that G has a node cover in size K is really just the argument we gave
for our example earlier. That is, we begin by, to construct the node cover by
selecting for each laws of E one of the literals that truth assignment A makes
true. We know there is one because A is a satisfying assignment, and the only way to
make a three-side expression true is to make each clause true. Then the node cover
consists of the two unselected nodes from each column. Notice that some of these
nodes may also have their literal made true by assignment A, but it doesn't
matter. The important thing is that the unselected nodes all correspond to true
literals. This selection of nodes has exactly K nodes, since K is twice the
number of clauses. So if we can prove that there's a node cover, then we have shown
that G has a node cover of size, at most K. In this case, exactly K. We claim the
nodes we selected include at least one end of each edge. So, indeed, we have selected
a node cover. First, consider the vertical edges. We selected two nodes from each
column, there are only three nodes per column so only one is un-selected. Thus
any edge in that column has at least one selected end. [sound]. And how about the
horizontal edges? Okay. Each horizontal edge has ends corresponding to literals x
and not-x for some propositional variable x. The truth assignment A has to make
either X or not X false. Whichever is false could not have been selected as the
literal that makes this clause true. Therefore, it s-, it surely is selected
for the node cover. That mean every horizontal edge is covered, and the case
selected nodes do, indeed, form a node cover. The converse also follows the
outline of the proof we gave in our example. So, suppose G has a node cover
with K or fewer nodes. Since all the vertical edges must be covered, there must
be at least two selective nodes in each column because one selected node can cover
only two of the three edges. We claim that from the nodes not selected for the node
cover, we can figure out a satisfying assignment for E. If there's un, an
unselected node corresponding to literal X, then make propositional variable X true
in the truth assignment. If there's an unselected node corresponding to literal
not X, then make X false. We'll see why this works on the next slide. Well what
could go wrong we might have made it through the sign mate that made some
variables true and false. That is no's corresponding to both literals X and not X
might have been outside the note cover. But that can't happen because there is a
horizontal edge between these two nodes and therefore one is in the node cover.
Thus, we do have a consistent satisfying assignment and the expression E is in
three sat whenever G has a node cover of size up to K. Now, let's revisit our old
friend, the knapsack problem. We're going to prove knapsack is MP complete. But it
is easier first to reduce three sat to a varientative knapsack which we'll call
knapsack with target. That is given a list of integers L and an integer target K, is
there a subset of L that sums to exactly K? Once we've show Knapsack with target MP
complete, we'll reduce it to the real Knapsack problem, which is given a list of
integers L. Can we divide L into two parts whose sums are the same? We have to show
Knapsack with target as an MP. But that, as usual, is an easy argument. Just use
the non-determinism to guess a subset of L. Then compute the sum of the integers in
the guest subset. And accept of that sum is exactly K. We're going to reduce
[inaudible] to [inaudible] with target, so suppose we have an expression e, in
[inaudible], and a target k. That e have c clauses and v propositional variables.
Regard to think of the integers in the list l we construct as written in the base
32. We can write them in binary so we need five characters per digit. But the factor
five is of no importance if we are only worried about performing the transduction
from three side instances to [inaudible] instances in polynomial time. The length
of each integer will be c plus v, so each integer can be as long as the entire
expression e. There will be 3C +2V integers. That means the length of the
output could be on the order of the square of the length of the input. But that's
okay, it's all poly times transduction, as long as we can generate the integers in
time proportional to their length, which we can. Here's a picture of some of the
base 32 integers we will use, those for the literals. Notice that each digit will
be either zero or one, but the base is still 32. We need a base that large to
avoid carries from place to place when we add integers. The high order of V
positions represent the variables. We'll have one integer for each literal, XI or
not XI, and thus there will be two V such integers. The integer has a one in the nth
position from the left and of the first V positions. If it corresponds to a literal,
based on propositional variable XI, that is it's either XI or not XI. The C low
order positions correspond to the clauses. The integer for a literal will have a one
in the position for each clause that it makes true. In all other positions in this
integer hold zeros. There will also be three integers for each clause. The
integers for the Ith clause have respectively the base 32 digits five, six,
and seven in the Ith position from the left end. All other positions are zero. So
here's a tiny example. There are two clauses and three variables in the, this
expression so c equals two and b equals three. Let's number the three variables x,
y and z by one, two and three respectively and number the clauses one and two in the
order in which they appear. Let's see the base 32 and [inaudible] is constructed for
this example, okay. First consider the literal x. There are three variables. So
the first three positions correspond to the variables. X is the first, so it's
position is at the left end of the first three positions. That's here. Thus we see
a one there and zero in the first two positions. The last two positions
correspond to the two clauses. When X is true, both clauses are made true, so we
have 1s in the each of the last two positions. Now, consider a literal not X.
The first three positions are the same as for literal X. But not X doesn't make
either clause true. So the last two positions are both zero. That is, these.
Here are the integers for Y and not Y. Among the first three positions, they both
have their ones in the middle, as they should. Y makes the first clause, but not
the second true, so, so it has a one in the low order position and that's the one
that corresponds to clause one and has zero in the second from last position.
These digits are switched for the literal not Y, because not Y makes the second
clause true, but not the first. And here are the integers for z. In the three high
order positions that each have one of the highest position as that. Likewise, e
makes the first but not the second clause true, so the two low order positions look
like the previous two integers. That is these are like those. Now let's look at
the integers for the clauses. For clause one we have integers with five, six, and
seven in the low order position. And for clause two we have the same digits in the
second lowest position. We'll pick the target as shown. Note that K in base 32 is
V1s followed by C8s. Thus, it is easy to write down and time proportional to the
length of the input to the transducer. The claim that when we add a subset of a 2V+3C
integers. There cannot be any carries from one place to the next higher place. We'll
see why on the next slide. In the high order positions, only two integers have a
one in any position so there can be no carries there. For the low order positions
corresponding to the clauses, each position has integers with five, six, and
seven there. Even if all three are in the selected set, that's only eighteen, not
enough. But what other integers could contribute to a low order position? Only
the three integers for literals that appear in the clause that corresponds to
that position. But these three integers only have one in that position, so the
maximum sum in any position is 21. So there are no carries. But we could have
made the base 22 instead of 32, but 32 is easier to convert to binary, so we went
with 32. The importance consequence of no carries is that the target can only be met
by making each position in the sum match the corresponding position of the target.
We'll see how this connects satisfying two of the assignments, the knapsack solutions
in the next slide. First, consider the high order positions, the positions for
the variables. If the sum of a set of integers matches the target, then the sum
must be one in that position. That means either X or not X is true for each
propositional variable but not both. That, in turn, means that the selected integers
correspond to a truth assignment. Now, let's look at the low water positions for
the clauses. The target has eight in that position. We can't have two or three of
the integers that have five, six or seven in that position. The sum would be too
great. The only way we're going to have integers that sum to eight in position for
a clause, is if, between one and three of the integers corresponding to the literals
of that clause are chosen. And we can use one of the integers, five, six, or seven,
to make up the difference, and make exactly eight. Now we need to prove the
construction we just gave works. First, I hope you see how to construct a single
integer for the output in time, proportional to the "n", which is built
the length of the input expression "e", and to with a constant factor of itself.
Since the number of integers is proportional to the number of clauses plus
the number of variables. And there can't be more than N variables in an expression
of length N. It is also sure that the number of integers in the output is, at
most, proportional to N. Thus, the output can be constructed in time, on the order
of N squared, and the transduction is polynomial time. We need to show it as a
correct reduction. As always, there will be two parts. First we'll show that if E
is satisfiable, then there is a subset of integers summing to exactly K. That is,
the output instance of the Knapsack with target problem has a solution. Then we'll
show the converse, that if there's a solution to the output instance then the
input expression is satisfiable. For the first erection, assume he is satisfiable
and let a be a truth assignment that makes e true. For a subset of integers we'll
start with the integers that correspond to the literals that A makes true. That gives
us the necessary one in the position for each of the variables that is the high
order positions. The integers we've selected so far make each clause true so
the sum in the positions correspondent to the clauses that is the low-end positions
will each sum to one, two or three. So for each clause, add to the set of the
integers we're choosing. The integer that has five, six, or seven in that position.
Whatever is needed to make the sum be eight in that position. Now we have a set
that sums to one in each of the high order positions, that is, the position for the
variables, and to eight for each of the low order positions, that is, the
positions for the clauses. That sum is exactly the target. So there is a solution
to the output knapsack instance. Now we must show the converse. Assume the output
instance has a solution, a subset of its integers whose sum is the target. First
look at the high order positions, those corresponding to the variables. The subset
of selected integers matches the target so it has one in each of these positions. The
only way that can happen is if we select exactly one of the two integers to the
variable corresponding to that position. If X is that variable, that means we pick
either the integer for X or the integer for non-X but not both. That means we have
a truth-value for each variable x. If we pick the integer for x itself and make x
true and if we pick the integer for not x, make x false. Either way the literal for
the integer we picked is true in this truth assignment. Which we'll refer to as
a in what follows. Now look at the position for one of the clauses. We
discussed earlier that with only five, six and seven available for a given position
we have to pick exactly one of them before we have to reach eight in that position.
But we can only reach eight if the selected integers for the variables have
among them something between one and three 1's in that position. That means the truth
assignment A must make each clause true. And therefore, A is a satisfying
assignment. We have now proved that when an output instance has a solution. The
input instance is satisfiable. That was the second of the two needed directions so
now we know that transduction is correct. The output has a solution if and only, if
the input is satisfiable. We're now going to prove the original knapsack problem is
NP complete. We'll refer to it as partition knapsack but it is exactly what
we earlier call just knapsack. That is, given a list of integers, can we partition
them into two disjoint sets with equal sums. We'll show partition knapsack to be
[inaudible], by reducing knapsack with target to it Remember, we already saw that
partition knapsack is an NP, but if you forgot, just guess the partition and sum
the two sets. Here's the essence of the reduction from Knapsack with target to
partition Knapsack. Suppose we're given an instance of Knapsack with target. Say the
list L in target K. The first thing we need to do is compute the sum S of all the
integers. That takes time proportional to the input length N. Now we can make our
output, which is an instance of partition knapsack. This output is a copy of the
list L followed by two or more integers. One of those integers is 2K, that is twice
the target. And the other is S, the sum of all the integers on list L. Here is an
example of a knapsack with target instance. The list l consisting of the
integers three, four, five and six and the target is seven. Resulting in some
partition match that has the same integers then 2K which is fourteen, in this case.
And five to the sum S of three plus four plus five plus six which is eighteen. This
instance of [inaudible] target has a solution. We can select the integers three
and four from L their sum is the target seven. The output instance of partition
knapsack, also has a solution. Take the integers in the solution to the input
instance. That is three and four. And include the last integer, the some of all
the integers on list L. Notice that both the selective integers three, four and
eighteen and the unselected integers. Five, six, and fourteen sum to 25, which
means we have a solution to partition knapsack. That turns out not to be a
coincidence. Including the integer that is the sum of L, always turns a solution in
the, to the input instance into a solution to the output instance. We'll see that
when we prove the correctness of this polytime reduction. So here's the proof of
correctness. And first, observe that the sum of the integers in the output instance
of partition knapsack is two times S+K. That is, the integers on list L sum to S.
And there's another integer S in the output list, so that makes 2S. And then
there is an integer 2K in the output list, which makes 2S+2K. Therefore, if we were
to partition the output list into two parts, each part must sum to S+K. First,
suppose the input instance of Knapsack with target has a solution. That means
there is a subset of L that sums to K. In the output instance we can pick this upset
of L plus the integer S to sum to S plus K. Of course what remains will also sum to
S plus K. So, we have a solution to the output instance. And conversely, suppose
there's a solution to the output instance. We claim that the two integers S and 2K
cannot be in the same partition because their sum is S plus 2K and that's more
than half the sum of all the integers in the output instance. Which recall is 2S
plus 2K. Now, if the output instance of a partition knapsack has a solution, then
the subset of l that is in the same partition as the integer as the sum to.
S+k. That's half the total. That means the subset of l sums to exactly k. Now look at
the input instance of [inaudible] sack with target. We just showed that there is
a subset of l that sums to k, so this subset is a solution to the input
instance. That completes the proof that the input instance has a solution, if and
only if the output instance has a solution. They therefore have a valid
polytime reduction from Knapsack with target, to partition Knapsack. And we now
know the partition Knapsack problem is also MP complete.