Lecture 06 : Part A

IIT Kanpur July 201
20 followers
1 Video View·Feb 2, 2024
[Music]
[Music]
so last time we
started uh
satisfiability studying the
satisfiability
problem so it was easy to see that sat
is in NP
because a satisfiable formula can can be
easily verified because if you are given
an
assignment but the harder thing is that
any problem in NP it can be efficiently
reduced
to the question of sat so take a problem
l in NP and we'll show why it can be
written as
a Boolean formula so the idea was that
you take the turing machine that is uh
or the ND team that is solving L you
think of it as a verifier during machine
m is a verifier which is looking for a
certificate you or which is given a
certificate U it will check
whether you certifies X via this
verifying turing machine
M
so U is something which you should think
of as formal variables unknown the
unknowns X is the known variable and in
terms of U we'll get a uh Boolean
formula which in the end we call
um okay we haven't reached the end but
so the formula will basically be
capturing how one configuration changes
to the next by the transition
function okay so configuration is a set
of uh variables as many as uh the cells
used on the tapes input tape work tape
so it basically captures this a0 Prime
to a prime t - 1 and a0 to a T
minus1 and of course the state and the
head
position right and we saw that uh first
we break it into the start
configuration compute steps and stop
configuration start and stop were
easy compute we further break it down
into steps right assuming uh
time uh T there will be T
steps so here is the the description of
compute going from C1
to uh
C2 right C1 was the start configuration
C2 was the stop
configuration and
uh essentially it boils down to checking
whether C3 to C4 configuration follows
transition
I of the transition ition function
Delta and that we can
capture the only Point here was that uh
while capturing
this one needs uh this K Prime and K
which are the head positions so what are
the head positions how will you find out
the head position in the middle of the
computation so that for that we actually
assume the touring machine to be
oblivious so
that the at the k
uh
step or at the I
step uh where the head is that will be
predetermined independent of
X okay this can be
assumed I as a function uh the head
position as a function of I this can be
assumed you don't need to know X or u u
anyways is
unknown but even X is not needed for
that just the length of X will be needed
so this will be an assignment
problem how do you convert a touring
machine into oblivious touring
machine and with
that since K is known as a function of I
so this step I can
be easily written as
a
uh as an and of equalities and
equalities you convert
into and or
not so it's a Boolean formula in the
end okay
so
next is uh
0.5 which
is so the formula that we obtained what
did we call it
did we call it
anything so in the end we get the
formula 5x
U and the property is
that F
XU is
satisfiable satisfiable with respect to
U right so you can fix U to be 01
string if and only
if uh use a certificate and hence the
tuning machine accepts and hence 5xu is
true which will happen
when if and only if x is a yes right
only if x is a yes string there will be
a certificate so maybe write that in the
middle if and only if
uh there exists certificate
U which will happen if and only
if x is an
L so this uh input string yes will will
be a yes string if a no if the formula
is
satisfiable and
uh what is the size of this
formula it's not a big formula right in
terms of T you can see that uh what we
have done is essentially we have these T
steps uh step I and uh within step again
there are
these
at most
uh uh T comparisons happening so it's
t² order
t² okay so this now finishes the
proof
thus we have reduced efficiently
reduced L to
sat and we write
it l less than equal
to
sat P referring to the polinomial time
reduction that we just gave right so any
problem in uh
NP reduces to
set and that is what
we promis to
prove
okay and uh in fact we can make this uh
CNF this formula five that we
constructed we can make it even more
special
the CNF
formula five can be reduced to another
formula can be
simplified to
S which is which has Clauses with only
three literals
such
that s is
satisfiable if and only
if f is
satisfiable okay
so in general of CNF you can always
convert
into uh cnfy you can always convert to
CNF SI which has only uh three literals
in each Clause this is called a 3
CNF so what's the proof of this
claim so uh a clause which has let's say
four literals we can break it up into
more Clauses each having three
literal by introducing a new
variable so idea is
convert a clause
with greater than three literals
to
um more
Clauses each
having three
literals we'll need a new variable for
this so let's just just see this in in
an example and that will
suffice so let's take five to
be
X1 X2
bar X3 X4
bar you can convert it
to
S where you look at the first two
essentially and the last two okay so you
use X1 X2
bar with a new variable
Zed and
then use Z
complement right so you can see that
these two are equal
so just
check that fi and S are indeed the
same okay because
uh um if both these Clauses are true
it's it's an and right so both these
Clauses are true so if if both are true
if suppose Zed is
zero then it means that X1 X2 bar part
is has to be true and if Zed is one then
it implies that X3 X4 bar part has to be
true so we have broken it into two cases
it's basically a case analysis so in
this
way any
clause in k
literals
has an equivalent 3
CNF right so this 3 CNF is as mentioned
before conjunction of
Clauses uh conjunction of dis
disjunctions where each Clause has only
three
literals and
uh the result that you get now out of
this is that three
set what is three set it's now
collection of satisfiable three
CNF so five such that five is a
satisfiable 3 CNF
formula so three set
is as
hard as
set right so so that is where uh we
are that if you are given in the
input conjunction of disjunctions where
disjunction are only on three literals
and the question is whether it's
satisfiable or not then that is as hard
as the whole of
NP okay three set is NP
complete so here one question that you
should do as an
exercise uh what about two
set
and
uh what about special cases of three
set okay so two set will have only two
literals in every
clause and you may also look at
uh settings between two set and three
set so you can come up with
such uh special cases and see whether
three set can be further
simplified okay so a hint is that two
set is actually in polinomial
time okay but there
are there might still be interesting
things between two set and three set
that you can come up
with uh so let us now formalize this
reduction that that we just
did so language
e is polytime car
producible
to
B to landage
B if there exists a polytime during
machine
M such such
that
x uh the question whether X is an a is a
yes
string of a or not this
question uh theing machine M will
transform X to M of
X in
B okay so polytime car producible means
that uh the that input you can transform
efficiently into a different string
which then corresponds to yes string of
B and it's if and only if okay this is
this is a very strong type of reduction
equivalence between a and
b and this is what we Define
as e reduces in a strong way so polytime
car
producible to
B so B is called NP
hard
if
uh every problem in NP reduces to
B
right this is the term you must have
heard uh
before whether a problem is NP hard or
not or just whether a problem is hard or
not so generally what is meant is that
uh it is so hard be so hard that if you
solve it then you solve every problem in
NP in this way by using a car production
po time car production reduction is is
there okay so strings are kind of uh
mapping from A to
B and uh finally NP completeness means
that b itself is in
NP so B is
called
NP
complete
if B's NP
hard and it's in
NP okay so it's
both NP hard and in NP then you call it
NP complete so the problem is complete
for NP
and uh we can again rephrase what we
have just proved as the following
theorem due to cook and
leaven that three set is NP
complete
right so this was shown half a century
ago exactly half a century ago that
three set is a problem which is NP
complete and uh till now what we don't
know
is whether we can solve it in polinomial
time right so conjecture is that NP
complete means that you cannot solve it
in polinomial time but there is no proof
though this completeness result we have
just
shown so we have
shown that for every language in
NP L reduces to polytime C producible to
three
set and also so threat itself is in
NP right there is no doubt because again
this three setat is just a formula so
when given an assignment you can verify
it in uh it Reve there is a verifier so
three set is both in NP and it is NP
hard so it's bound to be NP
complete so reductions
actually are very important in computer
science we use it use them all the time
they're also important in mathematics
but
uh somehow is it is not formalized as
such but in computer science we
formalize it and we use it all the time
reductions can also be thought of as
calling a program sub
routine right so you reduce your problem
and solve it somewhere
else that basically is the programming
idea consistent this reduction is
consistent with that programming idea
here so some easy properties of
reductions so if e reduces to
B reduces to
C then a reduces to C right this
transitivity is uh it follows from the
definition because whatever we you will
convert X in a
to let's say m1x in B and then convert
that to M2 of M1 of X in C take
composition and you have path from a to
c a reduction from a to
c so a is NP
hard and a is in
P so what does this mean if an NP hard
problem you have found an algorithm then
you have shown every problem in NP is
easy so you have shown that P is equal
to
NP
and if you have shown P equal to NP then
uh then any problem in P can be thought
off as NP
hard right so actually these two things
are
equivalent it's if and only
if so a is NP hard
and a reduces to
B then what What can you
do so NP hard problem if you are
reducing it to B then B must be harder
right so B is then at least NP
hard so that is the sense in which we
think of NP NP complete problems as the
hardest
so NP complete
problems are the
hardest in
NP right because to whichever problem
you will reduce it
to uh that problem will also become
uh NP
hard if it is a Yeah so basically this
third point is how we can read it like
this that NP complete problems are the
hardest every problem reduces to them
and if they reduce to something then
again by proposition
one
uh your new problem also becomes NP
complete so three sat a SAT and threat
are kind of the canonical
uh examples of uh NP complete problems
what are the other examples are there
other examples natural
examples so other examples
are which we which I mentioned in the
overview of the course first lecture
that traveling
salesperson subset
sum or sub suum integer
programming these are all NP
complete okay so these are some
practical problems which
are known to be NP complete how do you
show them NP complete first you see that
they are in NP that's
easy next you have to reduce from three
set to tsp to sub suum to integer
programming okay so every reduction you
have to work hard reductions may not be
very easy to come by so we'll not do all
these reductions in this course uh we'll
do some simple ones
but uh you can read off the literature
these
reductions uh it's not important for
this
course because there are actually
hundreds and thousands of NP complete
problems
known so hundreds of
uh NP
complete
have been
studied let's
see so NP complete problems may be
infinitely many but
uh there are hundreds which are
actually uh easy to
pose so-called natural
problems and people have shown
reductions they have given proof moves
that three reduces to all of
these so let us do one simple
reduction
so let's show let us show that
uh integer
programming is NP
complete let's see the proof sketch
um so we have already shown that it's in
NP let's restrict
to uh Boolean
solutions that is Xi is between 0 and
1 so if you restrict to this just 01
Solutions uh by introducing these
inequalities uh it's clear that uh it
will be an
NP because if there is a Boolean
solution somebody gives it to you you
can verify
it and uh now the NP hardness
part this will need more
work so NP hardness part we will
uh uh start with a 3 CNF let five be a 3
CNF
so let's
convert uh each
Clause to an
inequality okay let's do that
so for example if the Clause
is X1 or X2 bar or
X3 then you can write it
as so first of all we want
X1 X2 X3 to be between 01
right that is the first thing we want
because we want to identify XIs as false
and
true
next uh we want to make sure that X1 or
1 - X2 or X3 one of these
is at least one of these is
one so we just write that
down
this is greater than equal to
1 okay that's the that's the the uh
system integer programming system that
we have
written notice that X1 1 - X2 and X3 all
of them cannot be
zero right in other words X1 X2 bar X3
all of them cannot be false because if
that happens then you will get uh 1 less
than equal to
zero so this inequality actually is
implying that the Clause is true and you
do this for every Clause every Clause is
giving a new
inequality so that's the
proof so this implies
that three
sat reduces to integer
programming and integer programming with
just
uh with
Boolean uh
points Boolean
uh and just
uh three variables
three variables per
inequality right so it's very very
special you are not even using the full
power of integer programming you are
just using integer programs that have
uh that are only looking at 01 Solutions
Boolean feasible solu points and each
inequality has at most three
variables already this is
uh NP complete so since a special case
of integer programming is NP complete
General cases
also so this uh conversion which we
which we did from uh Boolean Clauses to
arithmetic this is naturally called
arithmetization
from
Boolean
cnf2 algebraic
polinomial this is called
arithmetization
can also call it uh
algebraization so this arithmetization
or algebraization is we are basically
making the original combinatorial
question we are bringing it into
arithmetic or
algebra so you saw this linear system uh
we can also get higher degree
systems which we'll get in the next
[Music]
[Music]
example
[Music]
