Lecture 06 : Part B

IIT Kanpur July 201
20 followers
1 Video View·Feb 2, 2024
[Music]
[Music]
so you have seen that uh integer
programming is is NP complete even under
great uh restriction so let's do this
arithmetization
more so
another
example or another way
to
arithmetization
another way to ariti
CNF
without
inequalities let's do
that the result
is quadratic equations Solutions of
those
so s is a system of
quadratic equations Modo
2 okay so these are en variate
polinomial degree 2 and you are only
interested in again 01 Solutions but the
arithmetic is
really model arithmetic mod
2 and S has a
root so now the this problem it's like
SAT but it's very algebraic because
we are actually looking for a root mod
two root of an narate quadratic system
so this problem is also NP
complete okay let's prove
this so in general uh finding Solutions
or roots of polinomial systems
uh that is hard okay these things are
really uh NP hard and here is your very
special example these are just quadratic
equations mod two even that is
NP so given
uh a
point x in
this uh finite field of two elements mod
2 to the end given this 01
Point uh
it's easy to verify whether it's a
root whether X is a root of
s so this this means that
uh quadratic equation 2 is in
NP okay so if there is a root it's a 01
root somebody gives it to you and you
can verify fast so that is what this NP
condition is so now comes the NP hard
part
so for
any 3
CNF
5 we convert each
Clause to a quadratic system mod
2
okay so instead of the linear
inequalities that we had before now
we'll
have uh quadratic system mod
2 so again we'll do this by an example
instead of going through the formal
proof so the Clause
uh
X1 or X2 bar or
X3 what do you want to do you want to
convert this into into a quadratic
equation mod 2 right so Clause convert
it
to yeah so this is trickier than what we
did before what what we'll do here is
we'll
actually um so when X1 is 1
uh we capture it by X1 - one
right being zero so let's first capture
that so either uh there is a solution to
this which means that
either X1 is 1 or Zed is Zer if Zed is
zero then we
have to rely on the remaining part which
is X2 bar and X3 so we write it as 1 -
X2 *
X
sorry X2 * 1 -
X3 right so either uh X1 is 1 or Zed is
z if Zed is Zer then uh
either X2 has to be
one oh sorry either X2 has to be zero
which is which makes the Clause
satisfiable because X2 bar becomes true
or X3 is one which again makes the
Clause satisfiable right so all these
cases are
covered and uh you can see that this uh
the these two equations they quadratic
mod
2
so this Clause is
true if I know leave the system as a
root right there is this if and only if
condition
and you do this for every clause in your
3 CNF
5 and you will just get
uh roughly double the number of
quadratic
equations variables
will uh will at most double if there
were n variables at most you you will
get actually n plus the number of
Clauses many variables so variables
don't blow up too much number of
equations doesn't blow too much and you
have what you
wanted so
similarly five
is
insert if and only
if
if only leave the
corresponding quadratic system has a
root right so that
implies that you have reduced three
set remember every formula we are
creating a system right just one system
is being created so this is a
polytime uh carp
reduction to quadratic equation
2 so that finishes
the proof of the proposition that system
polinomial system solving is also NP
hard but we have done it only mod 2 so
so you can also try the same
trick over other
fields I leave it as an
exercise so how about
uh quadratic equation
solving over other
fields which means finite
Fields field of
rationals uh field of reals complex and
so
on right so pick your favorite field and
see what you can do with this proof so
so this proof should
generalize and give you NP
hardness and uh if you can guarantee
that the solutions are small
then NP
completeness okay so you'll get either
NP hard or NP complete depending on what
the field is what your system
is okay so let us now uh move forward so
we have done complexity classes p and NP
so touring machines and
ndtm um now we can play with the
complexity classes create more
complexity classes first trick is the
cooperator co we call it co
classes so for language
l
we Define the co problem
as L
complement as just the complement what
it
suggests right so for a language L the
co- problem is uh complement of it
that's
simple and then for a complexity class
you can take the languages complement
them Define a new complexity class
that's the co
class so this
gives as Co
classes
as Co and P will be
what Co and P will will be the set
of L's such that L complement is in
NP right in other words you take
languages in NP complement them and
that's Co NP so you can do this uh
operation with any complexity class so
you can do it with p and then what
happens think about that so here uh
interpretation is so for
uh a
language l in Co
andp it is easy to
verify um so for NP it was easy to
verify whether it's a yes string with a
certificate given a
certificate uh here it will be easy to
verify whether it's a whether a input is
a no
string given the certificate so yes
becomes
no X not
NL given X and a
certificate okay so that's the
difference between NP and Co NP for NP a
solution can be verified for Co NP a
non-solution can be
verified right so it's
uh it's simple but at the level of
complexity class it might be a bit
confusing so the question for example
you can ask here is what is the hardest
problem in
Copp so what's the hardest
problem in Co NP like uh sat three sat
was hardest problem in
NP so three set complement is
automatically the hardest problem in
CP but we we can come up with a better
example a more
natural
sounding uh
definition which is
topology so toogy is the as the name
suggests these are formulas which are
true okay like
theorems so toogy is the set of those
CNF or in fact now it will be dnf so
fi
is dnf
formula and is a
toogy toogy is just another fancy word
for for a theorem okay something which
is
true but this is just using and or not
operators so it's a simple propositional
formula it's in dnf
form think of it as complement of CNF so
for NP it was CNF now for Co NP we are
talking about
dnf and it's true no matter what how you
fix the variables so um claim
is that this is the
hardest the
topology
is co NP
complete right which means uh which is
another way of saying that toogy is in
CP and every problem in CP efficiently
reduces poly time carp reduces to
topology so given
dnf
F we consider
CNF negation
five right so disjunctive normal form
it's
the disjunction of conjunctions that is
what five was when you do negation you
can write it as a conjunction
conjunctive normal form let me just give
a small example
here so dnf
uh if you have let's
say X1 and
X2 or
X3 so when you take negation do negation
of this uh dnf what do you
get you get X1 complement or X2
complement and X3
complement so this is what I meant okay
so you start with a
dnf this junctive normal
form when you take negation then it
becomes a
CNF
right so or of ands and of
ORS and uh the property
is that
uh negation 5 is
satisfiable so negation 5 has a
satisfying assignment right it means
that negation 5 becomes true which means
five becomes false which means that five
cannot be a
toy
okay this is this is an immediate
observation so which
means that
uh toogy is in Co
NP right so in fact let me do this step
by
step so we have shown that uh the no
strings of toogy they
have
verifiers which means that we have shown
topology is
in
NP
right which means that topology is
in Co
NP right that's what we have shown these
things are equivalent all these
statements are
equivalent so just by this negation
operator you can see that
uh uh what was s for NP now it is toy
for Co
NP but why why is
toy qup hard right that we have to now
check or we have to
prove so the co NP hardness
part let go over that so let uh L be in
Co
NP you have to reduce it to toogy so it
means
that there exists a poly
time during machine
M such
that every no string X can be
verified
for some constant C there is a
certificate of length x size of x to the
C such that
m x comma U is
1
and now for this touring machine uh
computation where use the unknown you do
cleav rediction uh proof and you will
get a formula so
now cook Len's
reduction on
M
gives a
CNF 5x
U such that what
happens such that X
is not in L if and only
if 5x U is
satisfiable right so no
string uh there will be a certificate
you
accepting path says that M accepts
X so this formula will
become 1 5xu at U right that is what we
have from cook
Leen and which means
what so which means that X is in L if
and only
if 5x U is so we are taking negation
right
5xu is not in set which means it is
unsatisfiable but when is a Formula
unsatisfiable it means that the negation
of it is true right if there is no
satisfying assignment which means on
every assignment it's false so negation
is always true so negation is is a toogy
right so X is an L if and only if
negation 5xu is a toogy which means
that we have reduced the problem L which
we started
with from Co NP we have reduced it
to this specific problem
topology so which means that toy
is Copp
complete right so it's not a hard proof
but you still have to go through
it
just to see how these things are done so
we have now two Notions for NP
completeness which
is three
set and then any problem to which you
can reduce three set to becomes also NP
hard and the second concept is co NP
completeness which is toogy and then any
problem which you can reduce toy to
becomes also inp
hard
and the open question is whether these
two concepts are the
same so is NP different from Co
NP okay
so are these
two in fact these two complexity classes
are they the same
which is equivalent to
asking whether toogy is in
NP which is also equivalent to asking
whether sat is in
Copp right these are all the same
questions because if toy goes inside NP
then everything in Co NP goes inside NP
so become Co NP becomes equal to NP if
sat is in a CO NP then whole of NP is in
Co NP so they become
equal okay
so whether all these concepts are they
the same or are they different that's
the that's the open
question also uh if it turns out that Co
NP and NP are the
same
then
uh then one can study polinomial systems
better
right so remember that uh polinomial
systems finding a
root that's an NP heart
problem and
U so if Co NP becomes equal to NP then
you are saying it's basically implying
that uh whether a polinomial system it
has a root that that has a very verifier
it doesn't have a root that also has a
verifier right so somehow in this
exponential space
uh somehow weirdly the search you will
understand
better okay if Co NP is equal to
NP so it will also have algebraic
consequences if you can show these two
equal although we don't we conjecture
that uh usually we conjecture that they
are
different
now uh some easy
propositions so p is equal to
cop okay if you think about cop uh where
it doesn't matter whether you are asking
yes string no string everything is
solvable in polinomial time so p and C
are the same
classes and compared to NP intersection
Co
NP both of them are contained right p is
contained in NP and P is also contained
in Co NP so they are in the intersection
that's easy to
see and uh if p and NP are the
same
then NP and Co NP will also be the same
because of P equal to
CP so which also means
that if you show that NP and Co NP are
different right if they are different
then p and NP is also
different so the open question of P&P is
contained
here
okay and
uh what is NP Union Co
NP so NP you can solve by you can find
the certificate in exponential time
right we have seen that so any of these
you can solve in X that's an upper
bound these are the simple
[Music]
observations
[Music]
[Music]
[Music]
