In this lecture, we're going to prove one problem, satisfiability for Boolean
expressions, to be [inaudible] by showing how to reduce the language of any
nondeterministic polytime Turing machine, to satisfiability. We will then cover two
of its restricted versions, called CSAT and 3SAT respectively. We'll learn shortly
what those mean. The first step is to learn about bullion expressions, or what
is saying. Expression the proposition of logic. These expressions consist of
constants, variables, and the operators and, or, or not. There are only two
constants, true and false. Which will usually represent by one equals true and
zero equals false. The variables can only take on these two values as well. The
operators and or not have the usual logical meaning when you write these
expressions you will use catenation [inaudible] that is no operating symbol or
and so. [sound]. X Y. Really means X and Y. We'll use + for or, so X+Y means X or Y
and we'll use the - sign for not, so -X really means not X. Here's an example of a
Boolean expression, X or Y is true when at least one of X and Y is true and not X or
not Y is true when at least one of X and Y is false so, the whole expression is true
when at least one is true and at least one is false. Since there are only two
variables that means exactly one is true and exactly one is false. As for any kind
of expression remember to use parenthesis to alter the order in which operators are
applied. The order of precedence with that is not first or highest, then and, then
or. Thus the parenthesis in the example expression are needed to make sure that
the ors are applied before the ands. A truth assignment is an assignment of zero
or one that is false or true to each of the variables of a [inaudible] expression.
In general, the key question about Boolean expressions is which truth assignments
give them the value true. But for our NP complete problem we need only this very
simple question: given a Boolean expression does there exist at least one
truth assignment for which the value of the expression is true? So this expression
is satisfiable. There are in fact two satisfying assignments, those that made
one of x and y true and the other false. But this expression, x and not x is not
satisfiable. There are only truth assignments. X can be assigned true or it
can be assigned false. If x is true than not x is false. That is, the and of
expressions, one of which is true and the other is false, has value false.
Similarly, if we assign X false, then X is false while not X is true. And, the and of
these is again false. We must see the SAC problem as a language just like all the
other problems we have discussed. First, the instances of the SAC problem are all
the bouillon expressions. Since expressions can have any number of
variables, we must code expressions in a finite alphabet. The parentheses, the plus
and minus can represent themselves. But we need to have a scheme for representing
variables. We'll represent the ith variable by the symbol X. Followed by I.
In binary. So here is an example of an expression coded this way. We have assumed
that x is the first variable so it is represented by an x followed by one. That
appears here, and also there. Y is the second variable so it is represented by x
and two in binary that?s x one zero. What we call the variables doesn't matter as
far as satisfiability is concerned, so we could have called Y. The first and X. The
second. Generally the easier part of proving of problem NP complete is proving
it isn't NP. Generally you just guess a solution and then in polynomial time, you
check it. And, the SAD problem is no exception. Okay, while Leeds described a
non-deterministic touring machine that can take a coded Boolean expression as input
and tell if it is satisfiable. And of course the non-deterministic machine must
be polynomial time bounded. In this case, order N squared time suffices. The power
of non-determinism lets us guess a truth assignment. We'll use a second tape to
write down the guess of a truth value for each variable. Then in the expression
itself replace each variable by its guessed truth value. We can now evaluate
the expression bottom up. You are not determining if the machine accepts the
value of the expression of this assignment is true. Notice the power of
nondeterminism here. The number of assignments could be exponential on the
length of the expression, but the nondeterministic machine works on all of
the expressions sort of in parallel thus appearing to finish in a time that is
polynomial on the input side cause we only count the time for processing one single
assignment Also, notice that non-determinism is more than parallelism.
Given any fixed number or processors, say a 1000, we can divide the time needed to
evaluate the effect of each truth assignment into a 1000 groups, and they'll
evaluate them in parallel. But if there are two to the N. Assignments it would
still take each processor time two to the N. Divided by 1,000. Which is still
exponential in N. We're now going to give the proof of Cook's theorem that the sat
problem is N., P. Complete. Since we don't have any N.P. Complete problems yet, we
can't do a reduction from some one other problem to sat. Rather we have to show how
to reduce any problem in NP to SAT in polynomial time. We do these reductions by
assuming nothing about the problem L that is an NP except that it has some
non-deterministic polynomial time bounded Turing machine that accepts L. To make the
reduction from these Turing machines to SAT easier, we're going. To make some
restrictions on the Turing machine. But, only restrictions we can assume without
losing any of the problems in n p. That is every problem in n p has one of these
machines which we'll describe on the next slide. The [inaudible] inscriptions we
make are the following. First, that the nondeterministic machine has only one
tape. And that the head never moves left of its initial position. We'll assume the
states are never also tape symbols so we can tell which symbol in an ID is the
state. Point three clearly loses us nothing since we can always change the
names of the states without changing what the machine does. And we're already seen
the constructions many tapes to one and two way infinite tape to one way. Each of
these constructions can square the number of steps the turning machine makes. But
that's okay. The square of a polynomial is still a polynomial. This slide has a
collections of random but important comments about what we assume about the
non determinates that poly contouring machine and, in addition to the
restrictions we've seen on the previous slide. First let P. Of N. Be the
particular polynomial upper bound on the running time of N. We'll be simulating M
on an input W, which is of length N. This next assumption is really about how we
define the next ID relation. We're going to assume that if M accepts W then there
is a sequence of exactly P of N moves from the initial ID with the final state in the
last ID, and perhaps other IDs as well. We're going to assume that if M is in an
accepting state then the identical ID represents one legal move. So if M enters
an accepting state early on, then the sequence of IDs leading to acceptance can
be extended to length P of N, by repeating the first ID that has an accepting state.
There's no harm in doing this, and it's already accepted, so entering an accepting
state more than once will not change anything. This is an observation rather
than an assumption. Remember that the head cannot move more than pvn squares and pvn
moves. So we're going to represent each i.d. By a sequence of exact pvn plus one
positions. The first pvn tape squares and the state. Initially most of these are
blank, but it's okay for some of these pvn plus one position to hold a blank beyond
where a head has reached so far. Even if this guide is not technically part of the
i.d. We have to design a polytime transducer that can turn the input w into
a brilliant expression that is satisfiable if and only if m accepts w. The transducer
is designed knowing M but not W. The first thing the translucent does, seeing W. Is
to determine its length N. The expression that is output from the transducer will
involve P. Of N. Plus one, all squared. What we call variables. But these
variables are not the propositional variables of [inaudible] and logic. Rather
they are collections of propositional variables that together represent the
symbol in a particular position of a particular ID. That is, the variable we'll
call X. Of I., J., represents the J. Position of the ife I.D. Thus I and J are
each in the range zero through P of N exclusive. Think of the variables arranged
in an array. The rose represents successive IDs and the columns represent
positions in those IDs. We'll start with the initial ID with the start state input
w and the rest of the positions blank. We'll design the expression to be
satisfiable if and only if M accepts W. We'll see that the expression constrains
the values of the variables, so that the only way that the expression can be
satisfiable, is if each ID represents a move from the previous ID, or the previous
ID has an accepting state and the next ID is the same. And the expression also
requires that of the final id iso p m is an accepted state. Thus from m which it
knows, w which it sees the transducer constructs an expression any satisfied
truth assignment for this expression will give the x as the proper values with the
id sequence of m with input w leading to acceptance. Now remember the x's are not
moving variables they represent states and tape symbols of m. However, each variable
can take on only a fixed number of values. The sum of the number of type symbols and
the states of the known turing machine M. Thus we can represent each XIJ by this
number of propositional variables, exactly one of which can be true. That is, for
each state or type symbol A let y sub IJA, that's this. Be a propositional variable
and we want y's of IJA to be true if and only if X of IJ equals A. As we describe
the construction of the Boolean expression we must make sure that we take time
[inaudible] is only a polynomial in N. There are many components from which the
final expression is built but they fall into two classes. Some depend on W and
therefore depend on N. These components are and must be of size that is polynomial
in N. And more importantly we can write them easily so that the time taken to
write them on the output is polynomial in N. The second kind is those that depend
only on M. These take a constant time as far as input size is concerned. That is, N
may have lots and lots of states and lots of type symbols, but these quantities are
independent of N. So as far as we're concerned, they're all just constants. And
to make our lives a bit simpler, don't forget that if an expression has a set of
arguments whose size is fixed independent of N, then no matter how large the number
is, it is a constant as far as N is concerned. So the time to write any such
component is a polynomial in N. In fact, it's a zero degree polynomial. Now let's
start to describe the output of the transducer. The output is an expression
and we want it to be satisfiable if and only if M accepts W. The whole expression
is the end of four sub expressions. Each of which enforces one of four conditions.
First is the sub expression we'll call 'unique'. It enforces the rule that there
is only symbol in each position of each ID. That is, the value of X, I, J is
unique. The second sub expression is starts right. It forces the initial ID to
be the start state followed by W. The next is moves right. This really should be
moves correctly but that's too many syllables. This expression enforces the
condition that each ID follows the previous ID by one move of M. And as that
convenient exception if the previous I.D. Has an accepting state then the next I.D.
May be the previous I.D. Finally comes the expression 'finish is right'. This
condition says that somewhere in all that stuff is an accepting state. For unique we
use the 'and' over all IDs, I, positions J and states or tapes symbols Y and Z of the
expression 'not Y sub IJ capital Y'. Or, not Y, I, J, capital Z. This little
expression is satisfied as long as at most one of the two bouillon variables, Y, I,
J, cap Y and Y, I, J cap Z, is true. Put another way, if X, I, J, were to have two
different symbols, say cap Y and cap Z. And one of these little expressions would
be false but unique is the 'and' of all these expressions and the entire
expression is the 'and' of unique and the other expressions. Thus, the entire
expression cannot be satisfied by any truth assignment that makes any pair of
variables, Y, I J, Y and Y, I J, Z, both be true. Now let's formulate 'starts
right'. This expression requires the first ID to be the one and that starts it with
input W. The W whose length is N consists of symbols A1 through AN. We want X zero,
zero, the first position of the first ID, to be the symbol that is the start state
of them. That's [inaudible], conventionally q zero. And we want the
next ten variables to represent W. This is, X0 I must be AI for all I up to N.
[sound] and all the other positions of the first ID are blank. That is, X0 I is blank
for I between N plus one and P of N. But there's a propositional variable for that.
Each of the conditions that makes up 'starts right' is of the form sum one of
the X variables is a particular symbol. But that's what the propositional
variables, Y, I, J, A do. So we can write 'starts right' as the 'and' of Y, sub
zero. Zero, Q.0, and. Why? 0-1-A-1, the first symbol of W, and Y-0-2-A-2 and so on
and after let?s say Y-0-N-A-N. Then you've got to have Y, zero, N plus one, comma,
blank and so on. So finish is right is easy. M accepts if and only if the last ID
has an accepting state because once M enters an accepting state it appears to
stay in that state until the ID number P of N. So take the 'or', the Boolean
variables, Y sub P of N, J and Q. Where Q is an accepting state and J is anything
from zero through P of N. Now, let's see how long it takes to write down the three
of the four expressions we have described. Remember, we have yet to describe the hard
one, Moves Right. Unique is actually the most time consuming. It requires that we
write down [inaudible] of P squared event symbols. The P squared comes from the fact
that we range over all I and J, between zero and P of N. The constant factor comes
from the fact that for each I and j, there're a large but finite number of
pairs of states and their tape symbols, each of which needs a little expression.
The number of pairs may be large but it is an independent event, so it is a constant.
So that expression involves two parentheses, three logical operators, and
two propositional variables. Only a constant number of things. But let me
remind you again, that the real issue is not how long the expression is, but how
long it takes to write it. But, the expression is simple and it is simple to
write the expression by looping on I and J. Thus, taking time proportional to its
length. Starts write is the and of P of N propositional variables, and again, the
pattern is simple. So, we can write this expression, in order P of N time. The same
holds for Finishers Write. They're a P of N propositional variables and we need to
output those variables connected by or's. Whoops. I lied. The running times are a
little bit larger than I said. Not enough larger to take us out of the Paulanolio
class, but larger by a factor of log in. That is, I cannot really output a
propositional variable, like wise of I., J., A., or even a constant time. The
reason is that we have to use a finite alphabet to represent order P squared of N
propositional variables. We agreed to represent a variable by the symbol X
followed by an integer in binary. Like this. To represent order p squared of n
variables requires interfusers length order log n. But this is no big deal. A
factor order log n is less than a factor of n so long as all we do is raise the
degree of polynomial by one, not even that much. So in what follows is we are going
to ignore factors of log n and just assume we can write down a propositional variable
in constant time and space. We are now going to start working on Newton's right.
A lot of this expression simply says that X.I.J. Equals X.I. Minus one J. That is, a
symbol in the IF ID is the same as the symbol in the same position of the
previous ID. That will be true whenever the symbol in that position is not the
state and neither are the positions to the left and right of the previous ID of the
state. Since a state can only move one position, we know nothing changes two or
more symbols away from the state. So, we're going to construct one sub
expression for each I and J, saying that, either, XIJ equals XI minus 1J. Or the
state is lurking about. The idea that the state is lurking is the or of those
propositional variables Y sub I -1KA. Where k is within one of I and a is state
symbol of m. Now we need to translate the quality of x I j and x I-1 j into
propositional variables but we just need the or of y I j a and y i. Minus one J, A,
that's this, for all symbols A. The reason that works, is that we already have the
need to enforce the condition that, for only one symbol A, can Y, I, J, A or Y, I
minus one, J, A, be true. The expressions we constructed for each IDI and position J
will be part of [inaudible] right. Each says colloquially that the [inaudible]
symbol can't change if the state isn't nearby. They will be [inaudible] together
with expressions that enforce the correctness of the moves of M. For the
case when the state is nearby. To write the expression for [inaudible] right, we
need to consider both the case on the left, where a position holds a type
symbol, and so do its neighbors to the left and right, and the hard case on the
right where the state is nearby. In the easy case there is no doubt that the
symbol in position J of the [inaudible] ID is the same as the [inaudible] symbol of
the I minus first ID. We already covered this case in the previous slide with the
expressions that if the state isn't nearby then the symbol doesn't change. But in the
hard case there are three positions. The positions that hold the state in the I
minus first ID and its neighbors that can be affected by the move. Moreover since
we're simulating a non-deterministic [inaudible] machine there may be a choice
of move, and we need to coordinate the three positions in the [inaudible] ID to
make sure that all three reflect the changes of a single choice of move. For
the hard case, the pieces of the move's right expression must do two things. Okay.
It has to pick one of the possible moves of M. That is the state of Q, it takes
symbol A in a direction that is the choice of one of triples in Delta of Q and A. And
then for that move [inaudible] force the condition, that when the J condition of
the id I minus one, holds the state Q. And the J plus first position of the I minus
first idea holds a symbol A, then in the [inaudible] ID the position J minus one
through j plus one, reflect that move. Note that either the J minus first or J
plus first position is unchanged, so the expression also has to enforce the
condition that this position is unchanged from the previous ID, that is suppose
delta of QA contains perhaps with other choices a leftward move going to
[inaudible] P and, and writing B over the A. That could be that. Then. For any
I.D.I. Position J. And tape symbol C. That is, this is. Id I-1, that's I, this is
position j-1, that's j and that's j+1, okay, then one possibility for the six
variables represented by this rectangle. That is this, is the combination that is
reflected here, that is. P has moved, lo, the state has become P. P is moved to the
left. The C is unchanged but its actual position is different, and the A has been
replaced by B. Similarly, if the move is to the right, but is something like that.
And the six values are the ones we must enforce from the variables in this
rectangle. And those, well, c doesn't change at all. The state q becomes p and
moves to the right. So it's at here, and then the a got replaced b and the b
appears over here. Now we can assemble the parts of moves right that enforce the
moves. We already gave the formulas that say, if the state is non of x, I minus
one, j minus one, through x, I minus one, j plus one, then x, I, j equals x, I minus
one, j. That is you can't change the symbol if the state is not nearby. Now we
have to include expressions that constrain the six variable Xs that are near the
state in the I minus first ID. For each possible move write an expression for each
position J and each ID I that expresses the constraints on the six relevant Xs for
that move. There is one more type of move of M that isn't really a move. We need to
allow no change in ID if M is an accepting state. For each accepting state of M
there's a fake move in which nothing changes. For each INJ take the [inaudible]
over all moves of M, of the expression you just wrote for INJ. Now, for each INJ you
have an expression that says that six relevant Xs reflect some move of M. Take
the and of these expressions over all I and j. Also include in the and all the
expressions from earlier that say symbols do not change if the state is not near.
Okay, there's a small glitch in all this material. The assumed position j is not
zero of p and n the left most and right most positions represented by the id's. If
J is one of these there are only four Xs involved. We need to modify so that the
missing symbols are assumed blank. This same fix up is needed for the rules that
say the symbol doesn't change if the state is not nearby. If the symbol in question
is in one of the end positions O or N then there is no possibility that the state is
outside this range and we can omit that requirement. Now consider how long it
takes to write down the moves right expression. Moves Right, consists of the
and of two P squared of and expressions, two for each ID I and position J. One of
the two is the expression that says the symbol doesn't change if the head is not
nearby. The other says that if the head is nearby then the six relevant symbols are
related in such a way, that they reflect one move of M. Each of these expressions
can depend on the number of state symbols and moves of M, but, none of this depends
on N. That is, as far as the length of the input W is concerned, each expression is
of constant size. The claim that each of the order P squared of an expressions is
easy to write down in time proportional to their length, by a transducer that knows
the moves of M. So, the transducer can now put moves right in time that is polynomial
in the length of its input W. As always there is another factor log n because we
must write the Boolean expression in a fixed alphabet, but factors of log n
cannot take us out of the polynomial class. So to sum up the proof of Cook's
theorem. It takes time less than order p cubed of n for the transducer to output
the Boolean expression that is the and of the four key components. Unique, starts
right, finishes right, and moves right. The claim that this transduction really is
a poly time reduction of the language of M to the language Sat First; if M accepts W
then there is some ID sequence that leads to acceptance. Imagine the P of N plus one
by P of N plus one matrix of the XIJs. The accepting sequence of IDs lets us fill out
this table correctly; giving the value to XIJ that reflects the sequence. The
expression we constructed will be satisfied only assigned to the
propositional variables, Y, I, J, A, the truth values implied by this choice of
XIJs. So if M accepts W then the expression is satisfiable. Conversely if
we have a satisfying assignment for the expressions we can get unique values for
the x I j's from the propositional variables. The unique expression assures
that the x I j's can be given unique values. And starts, finishes, and move
right assures that the X.I.J.'s form an accepting computation of M. With input W.
That is enough to show that every polytime non-deterministic turing machine's
language is polytime reducible to Sat. We now have one problem, Sat, that we know to
be NB complete. We're going to reduce it to other problems in order to show them NP
complete as well. But it is easier to polytime reduce a special case of Sat
called three Sat to other problems. So our first step is to show that [inaudible] is
NP complete even if the Boolean expression is in a very special form. The first
restriction that we place on expressions is, is that they be in C.N.F. That is
conjunctive normal form. These expressions are the end of clauses. And a clause is
the [inaudible] of literals. And a literal is either a propositional variable or its
negation. So, our next step will be to show to be NP complete. The problem C SAT,
which is whether a bouillon expression, in conjunctive normal form, is satisfiable.
Here's an example of a CNF expression. The first clause, this is X, or not Y or Z.
That is X, not Y. And Z. Are, each literals. The second. Clause is just this
not x. That's okay a clause can be for only one literal. The third is the ore of
four literals which are not w, not x, y and z. K, we are not going to reduce sac
and c sac, rather we will examine cooks proof and see where it needed to be fixed
up to make the output expression be in conjunctive normal form. That way we'll
have a direct reduction of every problem we need for c sac. Everything but moves
right is already in CNF. You can review the constructions, but when you do you'll
find that unique is the [inaudible] clauses, so is starts right. In fact, each
clause is only one literal, which is in fact an un-negated variable. And finishes
right is the [inaudible] of unnegated variables and therefore is a single
clause. Now let?s look at the most right. It is the and of an expression for each I
and j where I is id number and j position in that id. [inaudible] this expression
says [inaudible] is not near position j. And the symbol in position J of I, D, I is
the same as the symbol in the same position of the previous I, D or the head
is at position J in the I, D, I minus one. And three symbols of I, D, I around
position J reflect one move of the poly time Turing machine M. Here's the supple
thing. As complicated as these expressions are they depend only on M and not on the
input length N. As a result we can write the expression for given INJ in
conjunctive normal form. It is possible to convert any Boolean expression to
conjunctive normal form. I'll show you the trick on the next slide. This conversion
does in the worst case exponentiate the length of the expression but it doesn't
matter in this application because the only expressions to which we need to apply
the conversion are expressions whose size is independent of the input length N.
Thus, the time taking to convert to CNF for each expression is just some constant.
Independent event. Here's how we'll convert a given Boolean expression to C
and F. We'll consider each truth assignment that makes the expression
false. Note that if there are K variables in the given expression, there could be
[inaudible] such truth assignments and the resulting expression will take that much
time to write down. But again, we're only exponentiating a constant and the result
is still independent of the input size, N. For each such truth assignment, we
construct one clause. If variable x is assigned true in this truth assignment,
then the clause has literal not x. And if x is assigned false then the clause has
literal x. That way the only time the clause, which is the or of all these
literals, is false is if this is the exact truth assignment. The resulting CNF
expression is the and of the clauses for each truth assignment that makes the
original expression false. Thus, the CNF ex, expression is made false exactly for
those truth assignments that make the original expression false and therefore it
is, it is of course, true exactly when the original is true. For example, consider
the expression not X or YNZ. This expression is made false by three truth
assignments, those in which X is true and at least one of Y and Z is false. Let's
convert the first truth assignment, where X and Y are true and Z is false, to a
clause. Here is the resulting clause, since X and Y are assigned true, the
clause has, not X and not Y. >> Since Z. Is assigned false. >> [inaudible]. >> The
clause has Z. Without negation. Notice that the only way to make those calls
false. Is to make each literal false, which means giving each variable its value
from the truth assignment that generated this clause. The other two truth
assignments generate the next two clauses, that is, these two generate this and this.
And the entire CNF expression is the and of the three clauses. It is therefore made
false exactly when the variables are given one of the three truth assignments. A
bouillon expression is said to be in K conjunctive normal form or KCNF, if it is
the and of clauses, each of which contains exactly K literals. The problem, K SAT is
whether a KCNF expression is satisfiable. For example, the expression we derived on
the previous slide. Which we show here is in three, C and F. Notice it is the and if
clauses and each clause has, has exactly three literals. We're going to prove that
the problem three set is NP complete. The easy part, as is often the case, is that
three set is an NP. We already saw that the general problem set is an NP. Just
guess a truth assignment and check that it makes the expression true. Since 3-SAT is
a special case of SAT, the same non-deterministic algorithm were
[inaudible] 3-SAT. We're going to prove the, NP completeness of 3-SAT by poly time
reducing C-SAT to 3-SAT. We might suppose that the way to do that was to find a
polynomial- [inaudible] time algorithm to convert every CNF expression into a
logically equivalent 3-CNF expression. But not only can you not do that in polynomial
time, you can't do it all. That is their uploading expression simply had no c and f
expression. I'm not going to prove that formally, but an example is the expression
with four variables that is true if and only if an odd number of the variables are
true, that is if exactly one or exactly three of the four variables is true.
Fortunately, the reduction does not have to preserve equivalents of the input and
output expressions. Since we are dealing only with whether expressions are
satisfied all we need to preserve, as we transform the input expression to the
output expression, is that either both are satisfiable or neither is. Thus we're
going to give a poly time reduction that does not preserve equivalents. In fact, it
doesn't even preserve the set of propositional variables. Rather it
introduces new variables into clauses that have more than three literals, in order to
split them up into many clauses of three literals each. So, consider a clause with
K literals, X1 through XK, remember these are literals not variables, so any of the
XI's could be not, followed by a propositional variables. [inaudible] K
minus three new variables which we'll call Y1 through YK-3. These Ys appear in no
other clause and they're really variables, not literals. Also notice that if K is
equal to less than three, then no new variables are introduced. We're going to
replace the clause X1 through XK by K - two clauses, the first consists of. The
first two literals. X. One and X. Two. And the first new variable unnegated. That's
Y. One. The second. Which is this, has only one of the original literals, x3 and
two variables. The previous variable is negated while the next variable y2 is not
negated. That pattern repeats. Each new clause has in one of the original
literals, say that. A negated previous Y, and an unnegated next Y. Then finally the
last of the new clauses has the last two of the original literals and only the
previous Y negated. We need to show that when we make this change the new
expression is satisfiable if and only if the original expression was. For the first
direction, we'll show that if there is a satisfying truth assignment for the
original expression then we can extend this truth assignment to also provide
truth values for the Ys that will make the 'and' of all new clauses true. So suppose
that there is a satisfying truth assignment for the original expression.
Then this assignment makes at least one of the literals, the Xs true. Say it makes XI
true, then we can assign Y sub J the truth value true for J less than I minus one,
and assign Y sub J the value false for Y equal to or greater than I minus one. For
this truth assignment, the clause with xi, that is this one is made true by xi. All
the previous clauses goes there, and can be made true by their unnegated y's, and
all the later clauses, all of these. Are made true by their negating Ys.
Conversely, suppose that there is a truth assignment that makes all the new clauses
true yet makes none of the literal Xs true. Assuming that no Xs are true, the
fact that the first clause is true, that is this. Says that, Y SUB one, must be
true in this hypothetical truth assignment. And then, the second clause,
says that, since X, shh, so three is false and, not Y SUB one is already known to be
false, because we didn't, had to make Y1 true. That means that Y2 must be true. We
can reason the same way to show that all the Y's are true. But then, the last
clause, this, which has only false X's. And a negated Y, must be false. We have
shown that when we convert one long clause of the input to a sequence of clauses with
three literals per clause, the satisfiability or non- satisfiability of
the expression is preserved. We can repeat this argument for every long clause, thus
converting the original expression to an expression. But at most three literals per
clause, and that is satisfiable if and only if the original is. Technically
we're, we are not done because the original expression could also have
through clauses that are too short. For a clause with only one literal X, we
introduce two new variables Y1 and Y2, and replace one, clause by the four clauses
shown. Notice that the Ys appear in all four combinations. So if X is false, one
of these four clauses will be false, no matter what truth values we assign to the
two Ys. For example, if Y1 is true and Y2 is false, then this clause will be false,
whenever X is false. Conversely if X is true, then all four clauses are true,
regardless of the truth values of Y. And don't forget that these introduced Ys are
new. They appear in no other clauses just like the Ys we introduced to split apart
the long clauses. And the final case is a clause with two literals, say W and X. For
this clause we introduce one new variable Y and replace plus X by two clauses, one
with a non-negated Y, the other with a negated Y. Same argument as for the clause
of a single literal applies here. If a truth assignment makes both W and X false,
then one of the two new clauses will be false. But if the truth assignment makes
at least one of w and x true, then both new clauses can be made true. The
conversion of the clauses from the input C N F expression to clauses in three C N F
takes only linear time in the length of the input sequence. That is [sound], we
run through each long clause generating new variables and new three in literal
clauses as we go, taking time that is proportional to the length of the original
clause. [sound]. The constant of proportionality may be large, but the
algorithm is still linear. Well, we have to be careful as always to remember that
there is a finite alphabet involved. That means when we create new variables, the
Y's, it may take login time to write down their numbers, so the algorithm really
could take order and login time to generate, the output expression but as
always we'll ignore factors of login, they cannot take us out of the polynomial
class. We thus, have a poly time reduction from the problem c-sat to the problem
3-sat. And since c-sat was shown NP complete by the modified construction in
Crook's theorem that produced a CNF expression it follows that 3-sat is NP