Lecture 11 : Part B

IIT Kanpur July 201
20 followers
Feb 23, 2024
[Music]
[Music]
so in this way using the
ndtm of
a ndtm m of of the problem a uh we can
convert uh any input instance to a graph
instance and in the graph what all you
have to do is find the path from check
whether C start to C
except there is a path right there will
be a path if and only if x is a yes
string of a and all this can be done in
um the reduction is actually implicitly
ELC
computable remember that we call
implicit because uh call it implicit
because this work tape is too small to
store G comma s comma T so we cannot
store F ofx but we can access any bit in
that much
of
workspace so overall this
means that uh we have reduced A2
path
okay as claimed and LMA 1 and LMA two
now they together give you that path is
in
complete okay so directed reachability
is in and'll complete problem so solving
it fast means solving it better means
that you're actually simulating L better
than the trivial that's an open
question whether
NL equals L that's an open question a
corollary of this
theorem is that complement of
path this is co andl
complete right so path is in complete so
for the co- class take the complement
that will be coal complete using the
same
reduction so by the same f
uh so directed unreachability
that's the hard dis problem in Co NL and
the question you can ask again like NP
Co NP whether these two things are
equal whether NL is equal to co
NL and here there will be a big surprise
that we'll actually be able to prove it
so we can actually prove that NL is
equal to co NL and of course we don't
know whether it is it is
L so let's look at this amazing
proof NL equal to co
NL so this is a theorem by uh I mean
independently proved by two people so
immerman
and zlip zlip
Z it's an old result but it was a uh
stunning
result because PE in mean a prior people
people thought
that NL equal tol should be like NP
equal to NP
question but in this case actually
because of reachability being such a
special problem directed unreachability
actually converts to directed
reachability making NL equal to co
NL so let us uh look at this nice proof
this Elementary
uh proof it so what we will show is
uh it suffices to
show that
path
complement is in
NL right unreachability is in
NL so we
design
a lock space
algorithm
e such
that for input G comma s comma
T there is a sequence of
guesses
U for
a such that e will
accept he will accept if and only if
s2t there is no
path okay so note this uh negation so
s2t there is no path in the graph G
input graph G and in that
case there will be a certificate U for a
which a can verify in log space
right that is what we will Design so how
will we achieve this so the idea
is simple to State it is just by path
counting so count
paths in
G okay so it's by path
counting let's implement the
idea let me specify more
that count
Paths of length equal to
I in the graph G so it will be a
detailed a path counting in the given
graph and the certificate U will be
based on
that
is based on these
counts so let's do this let's implement
this
uh so let N
be the number of
vertices and c I be the set of
vertices reachable from
is uh in I steps at most I
steps so remember this
important object CI it's the set of
vertices which are at distance at most I
from The Source
vertex now immediate observation is
whether V is in CI for a
Vertex okay this
question
uh this question is in NL this is
certifiable in loog
space this question why is it in NL well
because if V is in CI
then there'll be at most I vertices
leading you from s to V so you can just
guess them one by one you guess them and
just like we showed the path
in uh NL the same
thing same proof works right that you
[Music]
remember so let's now
design
uh a lock space
machine Let's now
certify the
following in log
space so these will be more interesting
the first is uh
complement of
this right V not in
C how about that that is what we are
interested
in in the theorem
statement so we'll do this given the
size of C so
vertex V not in
CI given
CI
size
and now how will you find out the size
of CI that also you have to do in NL
right at least you have to certify it so
let's certify
this so CI equal to
C given the previous
one size of c i minus one and obviously
C C okay
so vertex not in uh
CIA this for this we'll actually use the
count the size of
CI and to compute the count or to
certify the count we will use the
previous
count right so so it will be a kind of
recursive
algorithm but remember it's just to just
a certification so it's not Computing C
it is just
certifying right whether this is the
correct answer so if we do
this do both these things in log space
then this will
imply that path is in Co
NL or the complement of path is in
NL right which will mean NL equal to
qul
why is that well because uh that's what
it is checking it is checking whether uh
T is
uh not in CN right that would mean that
SNT are disconnected using CT and CT
itself it will verify by guessing its
size and which it will verify by uh
going back back to CT CN
minus1 right so CN CN minus1 CN minus 2
those guesses can be made so by this uh
non- deterministic lock space
machine you can ultimately check whether
T is in is not in uh
CN so these two points 1 and two is all
we have to now
verify so let's do
it
so
certifying V not in
CIA given the
size so how is that
done so the
certificate of dis of unreachability
here
this will just
be uh guess all the vertices which are
in
CI once you have guessed them and
verified them check just check that V is
not
there so the certificate is
simply is the
list of
vertices
V1
so ordered let's say of ordered
vertices the certificate is an ordered
list of
vertices V1 less than
[Music]
vs2 dot
dot uh V the size of
CI
say that all of them are in
CIA and none equal to
V right so this will be a this is
clearly a certificate for V not in
CI you know all I mean you just guess
all the vertices in CI
and in this order and none of them
equals V and they are size of CI many
the only thing is how do you verify that
your guesses are
correct so the verification will be as
follows or well how do you correctly
guess
these so to do
this um
guess
VJ guess VJ VJ +
one and then
check
gu VJ less than VJ + 1 and
check that both of them are in
CI right that was discussed
before any vertex can be uh verified to
be in CI right that is by the path
problem in
NL so check whether VJ VJ +1 both of
them are in CI and then
finally
check that CI many
VJs
were correctly
guessed right so that's a lock space
machine which can guess the whole of CI
everything all the vertices it can guess
remember that doesn't have to store
it right because it is going in this
order so uh it'll just keep reusing the
space so reusing of space is important
here otherwise you will be out of space
because CI may be in in size see the
trick is that the during this uh ndtm
will just guess V1 remove it or guess V1
and V2 and then guess V2 uh V3 and V4 V5
and V6 and so on okay and keep checking
each
time whether that particular vertex is
in CI and you have done this CI many
times so keep a counter for
that so this is then uh doable in
NL that's what you learn
so it only
takes login
space and what have you achieved you
have achieved one point number one
certifying we not in CI given the size
of
CI next is to actually compute this size
by guessing right how do
you check that your guess is correct
size of CI C let's do that
now so
certify um uh so next what we will
do is okay let me change tactics
here
so two will be
done in two
steps so first what we'll be done
is
certify that V is not in
CI given the size of CI minus
one okay after this we will show how two
will be
done so let's do that this will actually
not be very different uh here you are
given CI minus one size not
CI but that is just uh moving to a
neighbor okay so it's the same
certificate will be similar so again you
the certificate is
is is again a
list V1 less than
vs2 it'll be shorter now v c IUS one all
of them should be in CI minus
one none equal to
V or V's
neighbor right so essentially
uh here you have
V and here you have a pre neighor of V
let's say U so since you are looking at
uh and here you have
S right so
um basically these uh CI
minus1
vertices they are at distance uh IUS one
from
s and you want to certify that V is at
distance more than I right so neither V
nor its neighbor U should be in CI minus
one right because if a neighbor is in CI
minus one then V also will be in V will
be in CI so that you don't want so hence
both V and U should be out of this so
that's that's the only extra
check so once you do this then you have
verified V not in
CI
so to do
this guess VJ and VJ +1
again like before right and
check that VJ VJ +
one they are in uh CI minus one
okay so that's
it finally
check that c IUS one
many VJs were
guessed
so this is identical almost almost
identical to the previous thing so even
when you know CI minus one that is
enough to certify V not in
CI by ensuring that both V and its prors
all the prors and in and
V they don't appear when we enumerate
cius
one right right so this is again
uh uh they are not being stored in the
workspace they are being guessed one by
one and then
checked that every guess is in CI minus
one and that these many CI minus one
many VJs were actually guessed so we
guessed
everything and uh that's a certificate
that V is not in
CI okay so finally coming to item two
which is
certify that CI is a given is is what
one has guessed
C given the length size of CI minus one
so how do you do
this given the previous size how do you
uh certify that the current size SI is C
so uh yeah the only way is you guess all
the C vertices so for
every V in the
vertex uh V in
CI
respectively V not in
CI are
certifiable
in log
space
given size of CI minus
one it's whether a Vertex is in Ci or
not in CI this we have shown that given
size of CI minus one it's certified
iable yeah so do you go over all the
vertices that's
all and count that gives you exact count
of
CI
so so go through
vertices in that order 1 less than
2 up to
n
and count the
correct size of
CI right so that can be then checked
with C compare with
C so again we it will not store the
vertic es or the information it'll just
store the count and uh it'll able to
certify whether CI is indeed C or not
right so that finishes both one and two
which
finishes our
proof so both one and
two
are
certifiable in L which means that NL is
equal to co
NL right 1 and two we have observed that
it implies an L equal to co so that
finishes the proof of uh immerman and
zeni
[Music]
okay
[Music]
[Music]
[Music]
