Lecture 07 : Part A

IIT Kanpur July 201
20 followers
1 Video View·Feb 10, 2024
[Music]
[Music]
yesterday we did uh we
start we started co- classes definition
of co-
operator so problem L Co problem is
simply the
compliment and collection of uh these
will give you the co- complexity class
so NP becomes Co
NP and we defined this problem called
toy which is collection of those so tau
is the collection of dnf formulas that
are
true okay so true means that every
assignment is a satisfying
assignment so it's kind of you can
already see that it's the opposite of
sat in a way and formally we showed that
tot is Co NP complete toogy is co NP
complete
problem and these are open questions NP
not equal to co NP this is not
known and equivalently whether tot is in
NP or sat is in Co
NP okay so we saw that if we can show NP
different from Co NP then it will imply
P different from NP okay so this is
clearly a very important
problem as important As It Gets in this
course so next is
NEX okay so this goes even above
exponential time this is non-
deterministic exponential time which is
a lot of time it's uh an ndtm that in
every step is making choices and
exponentially many choices are
possible so
it's
the non-deterministic version of
X okay so next
page Union
of n time 2 to n to 6
so this is non deterministic during
machines running for 2 days 2 to C time
and every possible
C we collect all these problems okay and
we call it
next which is short form for
non-deterministic exponential
time so so it's clear that
uh easy to see that P is in
NP NP is in
X and X is in
NEX right that's
obvious from the definition because time
is always in end time in the same
function right and NP is in X because of
EX exhaustive search for
certificates
uh but more interestingly what we'll
show is that these two questions are
related so this
question that these are different and
this question that these are different
these two questions are actually related
in a nice way so let's do
that so P equal to
NP implies that X is
next okay so this is an interesting uh
connection it is telling you that if n
determinism doesn't help at the
polinomial time level then it cannot
help at the exponential time level
notice that uh we are the theorem
doesn't say anything about the Converse
Converse we don't know so it's possible
that in exponential time non determinism
doesn't help but when the time is less
than exponential then it helps okay so
theoretically uh it that's a possibility
although we don't believe
it and the idea here is quite important
so the idea of the
proof is to pad a
language okay so the idea is that of
padding a language
with uh let's say
zeros that's the simple idea so
basically if you take
a so suppose we so we assume that P is
equal to
NP and L is in
next you want to show that L is actually
in X so how do you use the
algorithm let's say for sat to solve L
this problem l so the way you can do it
is you uh pad the language with a lot of
zeros exponentially many
zeros so let uh M
A 2 to n to C
time
ndtm accepting
L suppose L is solved by
m right solved in this sense
exponentially many Choice making
non-deterministic turing
machine so consider the padded
version
of L that is related to the idea
actually this L Prime
definition okay L Prime
is X padded with
zeros for the yes strings so take all
these yes strings and Pad them with
enough zeros
so that seems silly why should this
help so the reason why this will help is
that now the input length instead of
being n it's actually
exponentially
more okay now the length is 2 ra to n ra
to C and so now actually instead of L
being in next now L Prime is in
NP this is what you immediately
deduce so you deduce that
uh L Prime is in
NP why
because any X
Prime string in L
Prime
can be
accepted or is in fact is AC
accepted by
m
in
poly X prime
time okay so this ndtm m which was given
to you which we started with this
actually in as a function of X Prime
because X Prime has blown up
significantly to 2 ra to n ra to
C um it's actually being solved in
linear time in
that okay so then trivially LP Prime is
an
NP in fact I can just say bigo instead
of
poly even that is true solving it is
being solved in linear time so L Prime
is is triv in NP and uh which means that
L Prime is
in
P because we have assumed P equal to
NP so say l
Prime is in D
time n to D okay suppose so it's in
polinomial time so say that the time
complexity
is given by some constant D so n to the
D time so
now for n
x we can decide X in
L in
time
bigo
of
uh x + 2 to X to C which is this uh X
Prime in L
Prime that's the size of X Prime and in
that
D that thing rais to d right that's the
time complexity
which is upper bounded
by clearly
by uh exponential in
X let me just say
uh yeah that this is well this is just
single
exponential in size of X so this
means that L is in
X which and L was any
language in NEX so you have shown that
NEX is
X okay so this is how you will use sat
solver to solve
n and this was a surprisingly simple
proof not much happened here this is the
idea of
padding
what about the
converse so if you assume next to be X
then what does it say about sat are
there s solvers or not okay what is an
upper bound on NEX how hard are problems
or mean what is the Brute Force
algorithm to solve next
problems so that goes higher than one
level higher than EXP
right or exponential level higher than
x so we can define a complexity
class W exponential
time so e
x okay so e
is Union of D time 2 to 2 to n ra to
C right so instead of 2 ra to n ra to C
you raise that whole thing above two so
that's W exponential
time and uh again it's easy to see that
X is in
NEX and this is in
ex ex because uh it was an and NEX means
that there is an ndtm which is making
exponentially many choices so if you go
over all possible choices then
non-determinism can be eliminated but
the cost is the time complexity becomes
2 ra to exponential that's 2 to 2 to n
to C right and both these will be open
questions we don't know whether X is
same as NEX and we don't know
whether NEX is the same as or smaller
than
exp right just like we don't know
whether NP and
X are different and similarly we
can
similarly
um ndtm versus
TM gives
uh many complexity
classes okay just like you went from NP
to NEX you can keep keep doing this you
can now Define NE exp and so on and so
you can already build uh infinitely many
complexity
classes and some of I mean alternately
we will know that the classes are
different and alternately we
will have an open question yet to be
solved so we'll see which ones we can
prove so for example we can show that P
is different from X and X is different
from
exp okay we'll we'll start a topic today
with called hierarchy theorems there
we'll prove such
results uh but before
that let me give an example of uh a good
NP
problem which is which you can call
gudel computation question
so this problem
is
theorems so what is the language called
theorems uh this is
uh the collection of
those math
statements well formulated math
statements five that have a proof of
length
n okay provable math
statements hence
theorems so f is a math
statement so it's well formed by the
rules of
mathematics or the notation of math
so five is is a math statement with a
proof of
length at most
n okay so these are not fi is not false
and fi is not
unprovable right and the length is given
here so collection of these uh
theorems um where where does it live
right which complexity
class since uh proof verification is
easy we get the result
that theorem is in
NP right so the set of mathematical
theorems with their proof length this is
an NP problem because if there is a
proof given to you then you can
immediately check it right that is what
uh what is part of the mathematicians
work but this gives you an
interesting connection that uh between
between math and and this NP
completeness
area that if p is equal to
NP then what happens is uh every math
statement can
be um easily
resolved
right why is that because uh you come up
with some conjecture well formed
conjecture and you come up with a uh
length of the proof say the proof takes
100 pages right so you give your 5 comma
1 to the 100 pages to this uh sat solver
say you have a a SAT solver p is equal
to NP and then that solver will tell
you whether there is a proof or not of
length 100 pages right if 100 pages is
not enough you can try for 200 pages and
so on so a reasonable length proof
whether it exists or not can be easily
checked so this will essentially mean
that there is no need for mathematics
s right this is kind of automation of
what mathematicians do which is resolve
math statements well formed math
statements mathematicians study whether
and try to show whether it's false by
giving a counter example or whether it's
true by giving a proof and that will
become an automated
process
uh yeah so you can think of this as the
halting problem uncomp computability
that we discussed before so there the
time was
infinite versus finite and here it is
um within finite we are trying to study
that okay how fast or
slow can you find the proof okay so end
l proof can you find it in poly and
time
exponential
uh is Trivial it just follows from what
we had observed
here right NP is an
exp so theorems is trivially in X
because you can try out all possible
proofs of length n so that is not the
the issue uh but
then I mean this um computability is not
the issue here complexity
is so that is another reason
why uh PNP question is uh
philosophically very
interesting
okay next thing we will
do as promised these are the hierarchy
theorems
which is separating complexity classes
as much as we can
so the results you will see here they
will be of the Type U that when we fix a
resource let's say
time we'll show that if more time is
given we can solve more
problems okay and same thing with space
same thing with
non-determinism So within a resource
comparison can be made hierarchy is
there when the resource changes then
between two resources we can't compare I
mean we can't so those becomes open
questions but for a fixed resource we
will solve all those questions now so we
now see
that even strictly
more given
a
strictly more
resource so
example if you are given more
time more
space more
non-determinism turing machine can solve
strictly more
problems okay so the key thing here is
that one resource ource is being fixed
we are comparing one resource with
itself so more time or more space or
more nomism and then you can solve More
Problems P and P is not that question so
in P you are actually comparing time
with non-
terminis and then we have no clue what
to
do so how do these proofs
run so the idea in these proofs
is as mentioned in the beginning of
the in the initial weeks
uh this diagonalization
argument okay we'll use
the amazing method of
diagonalization to show hierarchy
theorems so use the trick
of diagonalization
to construct this extra
problem
okay so this was
uh done in
several works I think or maybe it was
one work with several authors so this is
the authors of this idea are heart
Manis
St
Louie
in the
60s okay so this
uh uh what the way you show halting
problem is uncomputable or the way you
show the basic property that real
numbers are uncountable they are
different from natural numbers or even
rational numbers that same idea actually
carries forward to
Computing and in fact complexity
Theory
to prove these hierarchy
theorems so the first thing that we will
show is uh about
time so theorem one
is that if you have more time by more I
will mean if GN
is strictly larger than F of
n log of f
ofn okay which seems like a weird
Condition it's not just that GN is more
than FN but it's that GN is strictly
more than FN *
log
then D
time of
FN is strictly smaller
than D time
GN okay so GN is this more time you can
solve more
problems that's an amazing
result so let's see how you prove such
things so as I said the idea is to find
an EXT actually design an extra problem
okay a problem which is in D time G but
not in D time F so what is this
problem so let's
design a turing
machine in the right hand
side okay a turing machine which is or a
pro I mean equivalently a problem in
right hand side that is different from
each
one
from each
one in the left hand
side so uh we basically have to
implement this uh diagonalization
idea for that what we will do is uh we
will let our touring machine run for I
mean we will take a turing machine in
the
input okay so and uh then our Universal
touring machine will simulate it for a
while for GN
steps and whatever answer it gets after
the simulation in GN steps it will
negate it okay this is also what we did
when
we uh worked with halting problem
so take a touring machine run it for a
while in this case we are truncating
this up to GN time and then whatever
answer is is
uh comes out of the simulation you
negate it and that becomes your
output okay and the we just have to now
do the calculation actual proof
calculation to verify what I said see
that it works so
consider turing machine
D which on input
X does the
following so if
X is not a turing machine
description
well if X is
not describing a touring machine it's a
don't care string we just output no then
output
zero
else
simulate
the turing machine that X is describing
right that M subx that is M subx
simulate it on itself so simulate uh the
turing machine X on
x but the difference from halting
problem proof is that this computation
has to be truncated because you
want um your turing machine to be on the
rhs right so rhs cannot take more than
GN steps or order GN steps so we have to
trun it at that so GX
steps which is GN
steps so simulate for those many steps
so either already touring machine has
decided something or not not yet so so
if it has
decided or if it doesn't
halt then output
zero this is again kind of don't
care answer I mean there was no answer
so you cannot do anything you just
output
zero most so most interesting comes in
the last which is
there was an answer of the
simulation and you negate that so else
output 1 -
MX X so whatever was the answer obtained
you negate it meaning 0 becomes 1 1
becomes
zero right so now it's clear that this
is a turing machine which is on the
rhs and we have to see what happens with
LHS
so D
decides a language
l in D time
GN right because it has only G of n many
steps so and let's say the langage it is
decided is l definition this is the
definition of l so L is in
rhs and the question
becomes is
L in uh left hand
side right so is l u in D time FN so
suppose
yes just for the SA of
contradiction so then it means that
there's a turing machine which takes
only F in time and solves
L and you can already see how the proof
how the contradiction will come because
in Step uh
2.2 in G of n
steps it is answering the opposite and
FN is less than
GN right so uh that is where the
contradiction will come because 2.2 is
negating that answer
whatever was supposed to come so let's
do this formally doing it formally will
take uh slightly
more
effort so let M be the
TM deciding
l in
time C * F of n
for
all n greater than equal to constant
n0 right this comes from the definition
of
uh D time
FN it's it's bigu of FN time so it's
actually C constant time FN after n has
crossed a constant
n0 so C and n0 are constants
and
uh yes so we will
now pick a large
string
describing
M so m is the is the touring
machine right which you are claiming
runs very fast and solves
l so we will actually pick a descriptor
of
Y and we'll get the contradiction out of
[Music]
[Music]
[Music]
that
