Lecture 05 : Part B

IIT Kanpur July 201
20 followers
Feb 2, 2024
[Music]
[Music]
so let's now go deeper into this
um start stop and it the main uh
complication will be in compute right
because that is where
the chunk of the T steps
lies so start is
simple so this will this is a Boolean
formula that
assults the start
configuration which is uh
SC1
variable this has to be Q of
s
and the pointers or the two heads should
be at the
beginning
and uh input tape should have X
and U because both X and U is the
combined
input and
finally work tape should be
empty
right so these are
the um conditions and we are doing an
and over
them that start asserts the start
configuration similarly
stop so this will assert it's a Boolean
formula that captures or asserts
that M
stops and outputs
one so which means that the state should
be
stop so finish
State and
uh work tape
header should come back to the original
position and we don't care where the
input tape head
is and uh work tape should have
uh the
accept the one bit at the
end well at the end or we actually can
we can be more
concrete and just say
that just demand that one is at the
beginning
okay
so so again this um state is finished
State work tape head has come to the
beginning and has put a
one in the beginning okay so it has
basically cleared the work tape and just
put the
output so the so these are the easy
Boolean formulas uh you can see that
just an and of of
uh uh equalities and equalities you can
Implement uh quite easily right in terms
of and or
not so let me
just show how so a equal to B condition
is implemented
as
as
uh either both A and B is
true or both are
false right so this for example
implements
um that two variables are equal either
both are true or both are
false and uh yeah the state variable can
take uh as many values as the number of
states but but that is finite and
constant right it doesn't depend on
input size so you can
actually do an uh you can check these
things bit by bit and using
this um this idea
this bit equality you can Implement also
for other
strings so for bits you can implement it
like
this and then you can extend it to
Strings equality of
strings right so with this let us now
move
to uh compute so what is
compute supposed to
do so this will
assert that there is a sequence of steps
following the transition
function
a configuration
sequence g0
to GT
minus1 of the turing machine
M starting from
C1
and ending at
C2 right so
basically this talks about their exist G
0 to GT minus
one so G 0 is C1
and GT minus one is C2
and uh for every I from 0 to T minus
1 I want to say that GI to GI +
1 follows a valid transition
step where I
means it is following some step given by
the transition function of
M okay so this part is basically saying
that configuration GI
to G +
1
follows transition
I given
by
Delta now transition function has only
finitely
many
um it's a finite description right it's
part of the finite control of the turing
machine
so what this uh for all I part of the
formula is seeing is
uh that GI to G +
one is coming from exactly
one
um command from the transition function
given by I and remember that uh number
of I is constant it doesn't depend on
N so number of I
is
constant right again this if you think
about the definition of touring machine
you will see that finite control doesn't
really depend on the
input does not depend at all on the
input so this number of I is constant
and hence this R is actually we are just
writing down every element
of the transition function one of them
will be followed by GI to G + 1 and then
we are going over all the eyes so you
just open this
up uh T
times okay do an
and so this is an and of T
things and of
t uh
formulas Okay so so that
is those are the comments and uh now
what remains is
uh
yeah so let me go back talk about
compute
again so compute has uh been broken into
three
parts
U starting from C1 which is g0 and C2
which is GT minus
one there are these
um G 0 to G1
transition and G1 to G2 dot dot GT minus
2 to GT
minus1 right so GT minus 22 GT minus one
all these steps have to follow
they follow some transition given by
Delta now this has to be implemented or
checked by the Boolean formula step so
we have to go there
now Define that what is
that so in general for for two given
configurations C3 C4 configurations
remember are given by
their um this array you can think of
this array or the data right State
pointers which is head positions and the
tape
strings um given this for C3 and for
C4 and also
given a transition I for from from this
Delta all you have to check in step is
the Boolean formula has to check
whether C3 to
C4 can you go from C3 to C4 in one step
using
I okay just a consistency check that you
have to do so you can reduce it to
basically equality tests and and over
that okay so this will be a bit
painful but let us anyways
go through
this so what you want is you want to
assert
that C3 to
C4 transition or
step
follows the transition
I which is from on state as B1
B2 under
the
um input head respectively
work tape head you have B1 B2 so from
there you go to state S
Prime
uh you can not change the
input but you can change the work tape
so make that B2
Prime and then what direction to move so
Epsilon 1 for input tape Epsilon 2
for work
tape right so I remember is given to you
when you are to define a step formula um
I is given and it is like this these
seven
values and C3 C4 is also given the
arrays are given now you have to do the
comparison so let's do that finish
it so for Epsilon 1 Epsilon
2 equal to let's say
stay okay that's one
case let's do this case
first
we use the
formula so this will be uh the state of
C3 has to be S why well because I needs
to
begin from s and go to S Prime so C3 has
to have state s and C4 S Prime right so
we are just implementing that or
expressing
that and
then
uh we have to now talk about the
positions of the input and work tape
heads so they are let's say k Prime and
K there exist these
numbers such
that
let me use a different color for
this K Prime
K such that P Prime
CJ sorry
C3 is
P Prime
C4 is K Prime that's because uh Epsilon
1 is
U is
T input tape yeah so uh input tape head
should not move so K Prime doesn't
change from C3 to C4 that's where the
head
is
and similar thing
for work tape
head okay
and now uh this transition I also tells
you about what was under the heads right
so this that was B1
B2
so here we implemented that
uh in the configuration C3
C4 the input tape
head started with B2 ends with B2
Prime and what else does the transition
want it wants
uh yeah B1 to not change so a prime K
Prime C3 is
B1 and rest of the input and work tape
strings don't
change okay so this is
the main implementation of
checking uh
whether a step was correctly followed or
not right this is the most local check
you are doing it's from one
configuration to just the next following
I right so this I hope is
clear and but I have implemented this
only for Stay
Stay uh there are three other choices
right in fact many more choices are
there because it's you can either stay
stay or you can stay go right stay go
left go left and go right and so on so
forth all these nine possibilities are
there so similarly for
other or analogously for
other analogous
expression or formula
for other Epsilon 1 Epsilon
2 right depending on what I was given to
you to define a step
I you can write down such formulas and
do the check for this given C3 to C4
whether it satisfies it so this Boolean
formula is true if and only if this C3
to C4 followed transition
I right that's that's what we have
achieved now some things are still
uh
Missing or I
should point
out so
remarks
so first uh point you have to note is
that X is
fixed X is a fixed
string because that was given to you in
the input
um but we'll take U as
a formal
variable why is that because remember
what was our original
goal our goal was to
uh show
that this problem l in NP can be can be
reduced to sat can be so basically we
want to express the uh verifier M
computation as a formula with variables
right so what will be the
variables the variables will be the the
certificate part the U part will be the
variables
so I should mention here that the ID in
the
idea
uh with
the unknown
certificate
okay
so the U will keep as the variables so
semantics being that if you exists then
the formula will be
satisfiable I mean or if the formula
ultimately satisfiable then there is
some U so that becomes a certificate or
if the formula is unsatisfiable then the
U doesn't exist there is no certificate
so that will tell you whether X is in L
or not right that that's the original
plan um this I have already discussed
that uh
equality on
strings uh can be
expressed
as a formula in CNF right that was
basically this thing that uh first do it
for bids and
then and this
over each and every bit of your two
strings so whenever I'm using equality
in the
formulas um formula description it can
be implement mented as CNF that's not a
problem when I'm using for all
I
operator right I use this for I for all
I less thanal to T minus
2 so this can be expressed as
ends
conjunction right you have basically for
every I we have given some some formula
and then do it around T many times just
copied that many
times that is not a
problem and
U the most important thing which is uh
which I'll not discuss here will will
not work out here is that
uh how to write this there exist K how
to implement this as a
CNF there exists K Prime K this thing is
tricky
okay because this uh remember K Prime
can take T values and same with K so
they are taking T Square
values uh but there exist means that you
have to take an
R disjunction right how do you write it
as
conjunction so this needs
a property of turing machine which you
will see in the assignment you will
solve it well also other issue is that
uh not just the or but Al another issue
is that K actually will depend on the
input exact string
x x u and step I
but UV have not even fixed U we are
taking as a variable right so actually
this is a bigger problem than just
disjunction because K uh really depends
on what step you are at step
I what is X well that we can fix because
because X was fixed that is still okay
but
uh yes I can remove X part but U we have
taken as a variable we want it to be a
variable so then K also becomes a
variable and then we cannot write this
expression as
CNF right so we need a uniform way um
for K Prime K to
be defined we somehow we should know it
already so the way it is
done is
uh assume
that m is an
oblivious cheing
machine that
is head positions
only depends
on size of
X and
I okay so it actually in a way only
depends on what is the step you are
at and uh you already know that function
function of N and
I you don't need U for
it okay oblivious machine doesn't need
to know X comma U so it's
not not X comma U that is not
needed so what this means is that
uh so K is known
as a function of Step
I and we do not need the Quant and we
can
express there exist
K as
CNF
okay so this oblivious touring machine
conversion is true for any touring
machine and uh it is without loss of
generality so you do solve this as an
exercise this we'll finish this
reduction next
[Music]
time
[Music]
[Music]
