Hi everybody I hope you can hear me uh give me a thumb thums up if you can good I see I see I see them coming through um so we're going to get started um um uh okay so getting back to what we've been doing um you know we we've been talking about space complexity um measures how much memory uh the algorithm requires or various problems require and um we uh defined the uh space complexity classes uh space f Ofn and non-deterministic space f ofn uh the polinomial space and non-deterministic space non-deterministic space classes and
gave some examples and so on and today uh we're going to pick up where we left off last time uh one of the examples which is going to be an important one for us is concerns this latter DFA problem so I'm going to go over that again uh give a little bit more emphasis to the uh space analysis uh which I got some Questions about last time and then we're going to move on from there and prove Savages theorem and then talk about complete problems for p Spas um and show that this problem tqbf which
we introduced last time is actually a pbas complete problem um but uh all in due course um a little bit of a review uh so we defined we defined what we mean by a touring machine to run in a certain amount of space that means it uses at most F of n if it's running in space f Ofn it uses it most F ofn cells tape cells on every input of length n and uh similarly a non-deterministic touring machine does the same but what's um in addition to that the non-deterministic machine has to Halt on
every branch of its computation and each branch of its computation has to use at most that bound that bounded amount of taste tape cells um so we're going to be talking about non-deterministic space computation today as well um it's going To be relevant to us um so we defined the classes as I mentioned um and the polinomial and uh the P space and non deterministic peace based classes and this is how they uh uh see how we believe they relate to one another um the classes Co NP and NP as well and of course uh
as I mentioned last time there are some very uh major unsolved problems in this area so everything could conceivably collapse down to p uh which would be of course be very surprising But we don't know how to prove otherwise um and the big theorem that we're going to prove today is that polinomial space and non-deterministic polinomial space actually do collapse down to each other um and being the same class so in contrast with the situation that we believe to be the case for time complexity where we believe the non-deterministic converting non-deterministic to deterministic gives an
exponential increase uh for space Complexity it only gives a squaring income increase as we'll see um so uh any questions uh on any of this um or we will just March into a little review of this latter problem um so re reviewing some of the notation and and let me emphasize that so the big theorem we're going to be proving today is that peace Bas and in peace Bas are equal um and also we're going to be talking about uh po peace based Completeness uh uh but uh both of those involve proving theorems um in
the in the first case Savage's theorem that convert conting non-deterministic to deterministic space is a squaring and in the second case proving that tqbf is ppace complete both of those theorems can be thought of as generalizations of the of of um this um theorem here that the latter DFA problem can be done in in uh the deterministic uh polinomial space or in Squared space um uh um so it really pays to try to understand how the proof of this theorem works because in a sense this theorem is a more concrete version of what we're going
to be seeing in those other two theorems in a somewhat more abstract form okay so um I like understanding things in a more concrete way first so that's why this is a good example to start out with but really in the end of the day it's the same proof just Repeated for those three theorems so this is are really three three for the price of one three three theorems one proof here so you're going to be seeing the same proof uh repeated three times um but in different levels of abstraction okay so let's let's review
again and I know some of you got it but um maybe some of you didn't and uh let's just try to uh be clear on the algorithm to solve the latter DFA problem so if you remember first of all let me just Jump on ahead the latter problem is you're give a lad first of all is a sequence of strings uh that change one symbol at a time that perhaps connect go from one string to another so you're going to go from work to play changing one symbol at a time so we gave an example
of this or you can easily come up with an example of doing this um but uh the computational problem is can you do it can you get from this string to that string and stay within a certain Language so it might be the language of English words or it might be the language of all strings that some specific D DFA um uh um recognize um uh recognizes so it might be all of the string these might all be strings that some DFA accepts or you know might be English words or some other rule um and
so uh uh that's what we mean by um trying to test if there's a ladder um and so uh the the latter problem is um well I Didn't I don't think I wrote down the latter problem itself but the bounded ladder problem is basically the same idea you're given a DFA you're given the strings u and v and now this is the bounded version of the problem where I'm going to give you a limited limit on the number of steps you can take so I'm illustrating that here so you're going to be given a b
and you want to say can I get from this string to that string within B Steps okay um and we had a notation for writing that uh going from U to V if there's uh a ladder that connects you Tov within it most B steps and so the bounded ladder problem which I'm introducing because I'm going to be aiming toward a recursive algorithm to solve this problem um is can I get from U to V by a ladder changing one symbol at a time where each string along the way is accepted by B and I'm
only allowed B steps little B Steps okay um so that is the computational problem that I'm going to be solving with the algorithm that I'm going to describe um so the algorithm I'm going to call BL for bounded latter problem um and uh here is the input and uh the algorithm is first of all going to look to see if B equals 1 if I'm just trying to get from U to V in a single step in that case it's a very simple problem because you want to test obviously that U and v are in
the you know are accepted by the automaton um and they just have to differ in one place and then then you have a very simple one-step ladder that takes takes U to V okay so for the case b equals 1 it's very simple uh for larger values of B we're going to use we're going to solve the problem recursively in terms of small smaller values of b um so for B greater than one we're going to Recursively test um you know if you're trying to solve the problem can I get from U to V instead
we're going to try e possible uh halfway through we don't know that it's halfway through so we're just going to try each possible string and we're going to test can we get from U the initial string uh to that new string that W in half the number of steps and can I get to the final string V in half the number of steps if I can do that Then I can get get from U to V the total number of steps B so I'm just going to try to do this one w at a time
for every possible W this is going to be very expensive in terms of time but we're not worried about time right now we're trying to cut down on the amount of space that we're using and this is going to be a big savings in space um let's not worry about the division B over two here all of the divisions when we're going to be seeing This several times going forward in in the lecture we can we'll think of them rounding up but I'm not going to cumber up make the notation look cumbersome by by writing
that every time um okay so here we go here is some candidate W string which is half halfway through um recursively test can I get from the starting string to that W and from W to that ending string um if I can if I find such a w then I accept and if I try all possible W and I Never man managed to find a way um to make both the top and the bottom work then I know I cannot get from D you know from the the starting string to the ending string within bsteps
and so I reject okay and now I'm going to solve the original unbounded ladder Problem by simply putting the biggest possible bound into the bounded ladder problem and that's his value T which is gives the very trivial bound of the the total number of possible strings that I Can write down within my length M that I'm working with so this is if Sigma is the alphabet of these strings it's just Sigma to the m that's all possible strings of course that's going to be a maximum size on the ladder um okay uh so now how
much space does this take and I think this is where people got a little bit um uh lost uh in in the lecture last time so I'm going to try to animate this um I don't know if that's going to help or not but you in The end of the day you're just have going to have to think through how the re how do you account for the cost of this recursion um okay but the main thing to start off you have to make sure you understand the algorithm you know to get from here to
there we're going to try all possible mid midpoints and then solve the upper part and the lower part recursively reusing the space that's the critical that's the way we're going to Get a saving by solving this problem reusing the space that we use to solve this problem okay so I'm going to I'm going to try to show this to you on actually how the space gets used on the touring machine you can kind of think of here's the input and then after that is going to be the stack for the recursion if you're not that
familiar with how to implement recursion doesn't really matter Um but you can just think about what the algorithm needs to keep track of um and so as it's trying every possible W so you know just in order like an odometer um just trying every possible every possible string eventually maybe it finds a string that's in the language um that here's an English word one of the first English words of length four that you might run into um and so now it makes sense actually to do the recursion um so that's all every time you you're
Going to have to have a register or a location on the tape where you're going to be writing down those different W's um so let's say it's over here and and we're just going to go through I hope that's not too small for you to see you know that's really where that action is happening um and finally maybe you got to the string W now you're going to try to do the recur so here is um you know as you're recur doing the recursion on the top Half again you're going to be cutting you're going
to be finding a new W for the the intermediate uh point just solving this upper upper problem where we're testing if I can get from work to Able later I'm going to have to deal with get getting from able to play um um go um so here again we're going to be trying fixing able fixing that the first W we're going to try every possible way of getting from work you know from the From the start string to that to that middle string um so we're going to try every possible thing here eventually maybe we
find some string um some other string in the language we get down to the string book um and uh that's all going to get stored you have to you can't forget this the string able but now we're going to use some more space to store those candidates so that's a second version of w um deeper in the recursion so here We're going to be trying all the POS possible strings here again eventually we get to some string book um and you know if that succeeds in getting us from uh work to Able via book now
we're going to jump down to do the bottom half um to see if I can get from able to play um as a separate problem which gets solved in the same space so now um here we're going to try all these Poss possibilities getting from able to play Maybe Call is the right intermediate String there um and so now um we're going to erase the book and now we're going to solve the lower sub problem in the same location I hope this is helpful there's a lot of work making these animations um and so uh
um I hope so the point of all this is every time we go down the level of the re the recursion there's another register whose size is big enough to hold one of one of the strings uh is Needed and that register gets reused um uh times as we're um at uh uh you know throughout as as we're going through through this recursion um so anyway I hope that's helpful um uh anyway so each level of the recursion adds another order in to record The W and so you have to how many levels do we
get well the depth of the recursion is going to be how many times we end up having to divide this picture in half to get until we get down to One and so the height of this you know when we start off is going to be um basically an exponential in m m is roughly the size of n so when you take the log of that you're going to get um uh you're going to um pull down the exponential so it's going to be order M or which is again roughly the same size as the
input m is like half the input because the whole input is u and v m is just the size of U um and so each level requires order n and the depth is going To be order n deep you know the log of the initial height of this U uh ladder and so the total space used is going to be order n squ okay so why don't we just take a minute I'm happy to spend a little time going through this either the algorithm's correctness um understanding the recursion or understanding the space analysis if there's
any question that you feel you Can ask that would be clarifying for you um jump in we'll we'll we we'll I I'll set aside a few minutes just to answer questions here um so I got a question here in step five why do we reject if all fail instead of just one fails um well here so remember what trying to do we're trying to say can I get from U to V in B Steps the way I'm going to be doing that is trying every possible intermediate string W um if I find some W which
does not work that doesn't mean that there's not some other W which might work all I need is one W for which I can get from U to W in half the number of steps and W to V in half the number of steps so I'm going to try every possible W if any one of them is good then I can accept if any one of them succeeds where I can get From U to W and half the steps and from W Tov in half the steps then I know I can get from u u
Tov in in the full number of steps um so I only need to find one if I if one particular one doesn't work I'll just go on to the next one um I okay here's a this is a good question um uh do we have to save the word book so once we succeed in getting from work to Able let's say via book do we need to Save that word book anywhere no all we need to remember is that we've succeeded in getting from work to Able we don't need to remember book anymore we just
you know remember that we've succeeded and that is by virt of where we are in the algorithm so we but you know if we have succeeded then we move on to this second uh recursion second call recursive call um so we we found some way to do it so we found some um some intermediate point which succeeds for This one so we move on to that one we don't have to keep any of that work anymore all you have to do is remember yes I can get from work to Able in half the number of
steps now I need what all that's left is to get from able to play in half the number of steps I don't doesn't matter how I got to Able in the first place so we don't have to remember that that was a good question though um so I think I I understand this to before we Replace um the value for book with call with the work involved to find Co um yeah we have to check that we can get from work to book and book to Able so we hang keep on to book while we're
working on the upper half and only when we've finally succeeded in getting from work to Able let's say via book then you can throw a book Away um but while you're working on the upper half you try book you try Different you know different strings of length four um until one of them Works um so I'm not sure somebody's asking me about breath for search and depth for search I'm not sure I see it um is I don't I'm not sure that's going to be a helpful way of thinking about this so I'm not going
to answer that right now but um you know you can ask that Offline later if you want why is the recursion why is the recursion depth log T instead of log M okay well how high is this thing initially um it's t high but every time we're doing a level we're calling the recursion we're cutting T in half first it's you know if you you know I'm solving this in general for B but we starting off with b equal to t t is the maximum size so initially this is going to be T and Then
it's going to be T over2 then T over4 so it's going to be log T levels before we get down to one um yeah so somebody's asking can we think of this as a memory stack yes this is like that's way a typical implementation of recursion is kind of with a stack where you push when you make a call and you pop when you return from the call um is it possible that V can appear During BL procedure on T is it possible that V can appear um I'm not sure what that means you can
V reappear you know so I'm starting with u to V is it possible that V might be one of these intermediate strs yeah you know um uh this you're going to try every possible intermediate string you know blind including V is one of them um uh you know if you can reach V more quickly well great um I guess what I have not Dealt dealt with the issue of what happens if you get to a um uh yeah Tech technically it's it's going to work out because I'm allowing you know the difference to be in
at most one place so even if you get there early you're allowed to not change anything and that still is a legal step in the latter um uh yeah I don't see how to do this from A bottomup perspective somebody's asking is there a bottomup version of this I I don't don't think so uh but no I don't think so all right why don't we move on um so now we're going to see this proof again but but this time we're going to be proving um that you can convert any um NFA to a DFA
with only a squaring increase so really uh Well let me just put that up put that up there um uh so this is going to be Savage's the that among other things proves that PE Bas equals npace base uh so it says that you can convert a non-deterministic machine to a deterministic machine only squaring the amount of space so you're comfortable with those notation here anything that you can do an F of n space non-deterministically you can do an F squar of n space Deterministically um and we're going to accomplish that by converting a you
know an NTM to a deterministic TM but only squaring the space used so n is going to get converted to m and now this proof is going to look very similar to the proof from the previous slide um it's the same proof um uh and um you know and and the fact from the previous slide you know about latter really is implied by this because you know we gave we had an easy Algorithm to show that the latter problem is solvable in in non-deterministic you know in NP space so latter problem was easily shown to
be in here um if you remember you just guess the you basically guess the steps of the ladder so non-deterministically you can easily check can I get from the start to the end um but uh Savage's theorem tells us that anything you can do non-deterministically in polinomial Space you can do deterministically in polinomial space so what we showed in the previous slide follows from this slide but this slide is really just a generalization of the same proof okay maybe I've said it too many times now um so we're going to introduce a notation very similar
to the notation we had last time but now we're going to be talking about simulating this non-deterministic machine with a deterministic machine and we're going to Have take two configurations of this non-deterministic machine CI and CJ and say can I get from CI to CJ in at most B steps I'm going to have a notation very similar to like the notation for the latter where I where I can get from this word to that word in it most be steps by a ladder here can I get from this word to that if can I get
from this configuration to that configuration with at most B steps of The touring machine's operation so these are two configurations now um of n so can n Go from this configuration CI to that other configuration CJ but only taking B steps along the way that's now the computational problem that I'm going to solve for you with an algorithm and it's going to be a recursion exactly like the previous one um so M gets its input the two Configurations CI and CJ and want and the bound B and want to check can I get from I
to J within B okay so now the picture is a little different um but very similar so instead of a ladder appearing here it's really something that's basically a tableau for um for the machine n where I have a an initial configuration and an ending configuration this would be hap this would happen to be um uh the starting point for the whole Procedure if you're testing whether n accepts W but we would be solving this in general for any config you know so with that case I have the start configuration of n on W and
the accepting configuration or an accepting configuration but um in general what I will be solving is starting with any configuration CI and going to any configuration CJ so I want to uh test can I get from CI to CJ within at most B steps um so First of all if B is one you can just check that directly um you know and now again this is we're operating deterministically to simulate the non-deterministic machine so this is the deterministic machine M so M can easily if it's given two configurations of N and says can I get
from the first one to the second one in one step well that's an easy check you just lay out those two configurations look at the n's transition function and Say is this a legal move for n yes or no and you accept or reject accordingly now if B is larger than one you're going to try all possible intermediate configurations I'll calling them CID this was like the W from the previous uh theorem this is all all possible strings C all possible configurations see mid and you know I don't you know a configuration is just going
to be a um uh uh Oh uh so far so okay this is all possible look like my PowerPoint crashed but it seems okay um look this is all possible configurations which is just a string with a string of tape symbols with a state symbol appearing somewhere that's all it is um going to try all possible uh configurations as candidate middle configurations and say can I get from the upper one to the middle to this candidate middle one and from that Middle one to the to the lower one within half the number of steps each
time so um and solving that problem in cursively um okay um so I I got a question here about the possibility of looping forever um uh first of all if n is going to be looping I don't have I don't have to worry about it because um I'm starting off I'm only need to simulate machines that that always hold that are deciders because I'm trying to show that any Language in here has to be accepted has to be uh has to be decided by some some not deterministic machine so I'm not going to worry about
machines that are looping if they're looping you know um uh M may be misbehave in some way but that's not going to be a problem for me um so let's only let's keep life simple think about the Mach deciders only um okay so we're going to recursively test here so that means I have a going to try every possible middle see if I Can get from the the start to the middle and the middle to the end um uh if both of them work for my if my I test them recursively then I'm going to
accept if not I'm going to continue and I reject if I try them all and none of them have worked then I know there's no way to for n to get from this configuration to that configuration in bsteps okay [Music] Um and the overall picture I test whether n accepts W as I mentioned by starting the c i is the start configuration and CJ is an the accept configuration um and now how big is T because I need to calculate a bound on how U many How deep the the the the recursions are going to
be um so T here is going to be the total number of possible configurations um you know if this is whole thing it never repeats a Configuration so this is going to be a bound on how many steps and can be taken and that's simply you know we calculated this before it's the number of um uh States times the number of head positions times the number of tape contents tape contents and this is really going to be the dominant um consideration anyway and so now each recursive level and maybe I should have emphasized this at
the beginning how wide is this picture it's Big enough to store a configuration configuration is essentially a tape contents so that's going to be F of n wide so each recursive level stores one configuration now the W cost F of n space to write down and the number of levels is going to be the log of the initial height which is this so this is going to be the dominating uh part of it so the log of this is going to be again order F ofn so This each one takes f ofn space to write
down the depth of the cursion is going to be order F of n so the total is going to be order f^ s of N and that's how much space this this uses and that's the proof of Sav Savages there so yeah so there's a good point there uh I was thinking some somebody asked can there be multiple accepting configurations I should have made the I I I forgot to say this but and I was just realizing it as I was Explaining it one of the things I should have you you can enforce that there
is just a single accepting configuration this is kind of a detail but so don't worry about it if you if you don't if you don't want to but you can make sure that there's a single accepting configuration by telling the machine when it accepts it should erase its tape and move its head into the leftmost cell in the accept configuration so there's just going to Be a single accepting configuration to worry about instead of having to try multiple uh possibilities which you could do in this algorithm but it would just be annoying to have to
write it that down that way so we often assume there's just going to be a single accepting configuration for these machines um um okay so this is how do you know f ofn um so that's a that's actually a little bit of a delicate issue Uh I mean if you could compute f ofn um the bound which is for for example if it's going to be a polinomial bound you could just compute F ofn it's very easy to compute n s or n cubed if and so you can just um uh compute that and then
use that as um the size of the registers you're going to be writing down um for if you want to prove this in general for f ofn it's a little bit technical to have to deal with it um and I'm going to have to refer you to the Book on that one the book tells you how to do Sol this for a general fent you basically have to try every possible value from one until it works um and uh I'm afraid that's going to derail us trying to un decipher that so let's not worry about
that aspect of it but it's it's a it's a you can handle general f ofn here um you don't need to put any conditions on f ofen um can we go over this term here so we've Seen this term once before when we talked about lbas and and seeing that LBA is always uh we can solve the Alba problem this is simply the number of different configurations the machine can have um because the configuration is a state it's a head position and a contents of the tape and this is the number of each of those
that that you can Poss POS have number of states head Position you know the size of the tape of f ofn is f ofn so this is that many different head positions and this is the number of if D is the size of the tape alphabet this is the number of contents tape contents that you can have um okay how is seeing if n accepts W with this algorithm convert non- deterministic turing machine to some determinist touring machine well n is the non-deterministic touring so n is We're converting non-deterministic touring machine n to deterministic turning
machine M so m is a deterministic simulator of n that's what this whole M is so if we can do this for you know for any n that we' proved our theorem um okay why don't we defer I think you know we're I think I got through most of the questions here if there's other things we can save them for the um uh coffee Break which is coming soon I think we have one more slide before that um okay so I'm going to Define peace based completeness I think yeah and then I think I think
after that we have the uh the break uh so peace based completeness is defined and in very much inspired uh similarly to NP completeness um so uh a problem is PE space complete if it's in PE space and every other member of Peace base is reducible to it In polinomial time and we'll say a bit about why we choose polinomial time reducibility here um so here's a kind of a picture of how peace Bas or how complete problems of you know uh relate to relate to the their complexity classes so you kind of think of
a complete problem for a class it's kind of the hardest problem in that class because you can convert you can reduce any other problem in that class to the complete problem so here the NP complete Problems sort of the hardest for NP here the P space complete problems kind of the hardest for p p space if any if an NP complete problem goes into P that pulls down all of NP to P if any pbas complete problem goes into P it pulls down all of P Bas into P by following the chain of reductions um
because any pe-based problem is reducible to the complete problem which in turn if it's in P then everything uh goes into P so if you have a PE Bas complete problem Which is in P then all the PE base goes into P um so why do we use polinomial time reducibility and say instead of say polom space reducibility when we Define this notion um it's kind of a very reasonable question but if you think about it using polinomial space reducibility would be a terrible idea um because and we've seen this phenomenon Happen before every two
problems in P space are going to be P space reducible to one another we haven't even defined that notion yet but you can imagine what it would be because a pebas reduction can solve the problem um for a problem in P space and then it can direct its answer anywhere that it likes so in general when we think about reductions the the reduction should be not capable of solving the problems in the class because if they could um then Every two problems in the class would be reducible to one another and then all problems in
the class would be complete because everything would be in the class would be reducible to any one of the other problems so it would not be an interesting notion what you want to have happen is that the uh reductions should be weaker than the power of the class and so um uh every um you know and if you if you look at the reductions that we've defined so Far they're actually very simple you know the only thing is yeah they have to make sure that they can make it that they can make the output uh
big enough but actually constructing the output they do very simple transformations in fact even polinomial time is more than you typically need there's even much more limited classes that are capable of doing the reductions as we'll see um so having powerful reductions is really not in the spirit of what reductions are all About you want very very simple transform Transformations um to be the reductions anyway hope that's helpful so what what we're going to be aiming for in this second part of the lecture is showing that tqbf is pie based complete um and let me
he has a check in uh uh so this is our first check-in um coming a little late in the Lector suppose we have proven that as we will that tqbf is PE based Complete uh what can we CL conclude if tqbf is actually not necessarily in P only goes to NP that's and this is relevant to a question that's coming in from the chat but I'll answer that later so um suppose tqbf ends up being an NP and not in P what what can we conclude remember if it if tqbf is in P then P
space equals P suppose it goes to NP what happens then check you know there may be several uh correct answers Here so check all all that all that apply all right so we're near the end um of the uh poll so let me give you another 10 seconds and then we're going to shut it down um okay we all are we all in closing it down um here are the results so yes so uh first Of all the most reasonable solution most reasonable answer is B uh which I think uh most of you have gotten
that if you know if peace based complete problem goes down to NP well NP is capable of simulating the polinomial time reduction um and so um any other problem in peace base would then also be an NP and PE B would equal NP but note if P Bas equals NP there also NP equals Co NP um because peace base itself is closed on you know is closed under Complementation so that was kind of a little bit extra fact that you could conclude from this as well um so let me let's move on then to our
uh Kofi break and uh we'll pick up the proof that tqbf is peace based complete um after after that okay so so was D true or not um D was P equal NP no D we cannot conclude that P equals NP um if um from pspace uh equal to NP um so if tqbf is an NP it doesn't tell Us anything it's f for all we know P equals NP but uh from the stuff that we've that we know so far we cannot conclude that P equals NP um oh and yeah so you can conclude
oh I'm sorry you you can B and D are both correct here um let me just shut this thing off uh so B and D are correct so if if a p Bas complete problem goes to NP then NP Equals P Bas and equals Co NP so the correct answer B and D sorry I I got myself confused so C but C is not something you can conclude or a okay uh so somebody say somebody's asking me a fair question you know I say the reduction method should be weaker than the class uh but you
know for example even in the case of P space p space might be equal to p and then um it wouldn't be weaker than the class if we use Polinomial time reductions but um I think maybe I should say apparently weaker uh as far as we know it's weaker uh but we believe it to be weaker if it's true if P equals P space then every problem in P is going to be P space complete it's just going to be a weird world if P equals P space similar same thing for NP and NP um
so so I'm getting a number of questions also about other possible reducibilities that are even weaker than Polinomial time reducibility um so we're going to see uh um very soon weak or reducing you know complexity classes within P so first of all P space seems to be bigger than P we're also going to look at log space but that's going to be um actually in Thursday's lecture those are these are classes in that seem to be inside well they're inside P they may be proper we believe they're properly inside P but we'll we'll see that
later um let me just see Here really should have so we're we're almost out of time uh let me put our timer back in fact our timer is showing us out of time so um why don't we um uh get going let me move this um back to okay continuing peace tqbf is peace based complete so first of all let's remember tqbf um uh these are all of the Quantified Boolean formulas that are true so tqbf stands for True Quantified Boolean formulas um uh and remember we saw these examples from the previous lecture um uh
that you know here these are two Quantified these are two qbfs um the first one is true the second one is false and and you it's kind of interesting to think about you know here they're exactly the same except for the Order of the quantifiers and so what's really going on you know here uh just I think it's good to understand these Expressions they come up everywhere in mathematics uh these Quan quantifiers um you know in the upper one uh when we say for every X there exists a y that y can depend on the
choice of x you choose to make a different X you're allowed to pick a different y but this but the lower expression says there's a Universal y there's some one particular y that works for every X so in a sense um uh the lower statement is a stronger statement um you know whatever you have in the inter the quantifier free part uh so the lower one implies the upper one happens that the lower one in this case is false and the upper one is true but in general the lower in the you know when you
have this change of quantifiers like this the the um the lower one would Imply the upper one okay anyway that's sort of a side remark so um let's get back to the proof that tqbf is PE based complete that's what our goal is all right um now as I mentioned this is the same proof going to be seeing it for the Third third time today but you know there's a certain amount of it's sort of the context changes uh in each case so now uh we want to show that tqbf is peace based Completed so
it's one of these hardest problems now but for p space um where satisfiability was like a hardest problem for NP uh so we want to show that every language in pspace is reducible to tqbf um and so we're going to give polinomial time reductions that map some particular problem a which can be done in space end to the K it's A problem solvable in PS space we're going to show how um f Maps a to tqbf we have to construct the F so f is going to be a mapping that Maps strings which may or
may not be an A so strings W which may or may not be an a to these formulas these Quantified formulas um so uh W is going to get mapped to some formula f sub MW it had exactly the same even symbols we used when the proof proof of the cook Lev theorem about sat being NP complete this Is a very similar proof um but you'll see that we have to do something more in order to make it work in this case uh so if W you know W is an a if and only if
this formula is going to be in tqbf in other words if if and only if this formula is true um so this formula is going to kind of Express the fact that M accepts w which means that W is an a because m is the machine is the peace based machine for A so this uh formula says m excepts w and it achieves that by building in a simulation of M on W it kind of describes a simulation for M on W which ends up accepting and if M does not accept w you that description
is going to inevitably be false um okay so let's just see how that's what that's going to look like uh so We're going to use the same idea that we initial that we used for the cookle theorem that sat is NP complete this notion of a tableau so if you remember that we had it was basically a table which ways was just simply a way of writing down and a computation history for MW okay so the rows are the steps of the machine um the top row is the start configuration the bottom row is let's
say some Particular accept configuration such as I just described where the machine clears its tapes and moves its head to the left end so there's only one accepting configuration we have to worry about okay and each of the rows here is a configuration of M of M okay um because M runs in space into the K the Tableau kind of similarly to what I described before has width into the K So now you know we're talking about polinomial time machines so the F which is the bound the Space Bound is going to be some polinomial
n to the k so the width of this uh Tableau the size of these configurations are going to be n to the K how high is this Tableau going to be well that's going to be limited by the possible running time of the machine um which is similar to what we saw before um it's going to be Exponential in the Space Bound so it's going to be D to the end of the K where D is the essentially the tape alphabet of the machine okay so are we all together on this this is um very
similar to the proof of set is NP complete the key difference there was M was non-deterministic um which might be something to think about later but let's Not focus on that right now here this m is deterministic and um but the important difference was the shape of the Tableau the the the the the size of the Tableau was very different in the case of sat is NP complete we started off with a polinomial time non-deterministic machine so it only could run for a polinomial number of steps here is a polinomial space machine which can run
for an exponential number of steps That's a that's going to be an important difference here so let's let's see why uh the reduction has to construct this um Formula F sub MW which basically says that this Tableau exists now we already saw how to do that when we proved the cookle theorem that sat is n be complete remember we had all of those we had variables for each cell that told us what the contents of that cell were was And then we had a lot of logic here we had a bunch of logic that said
that those all the you know those neighborhoods were correct which basically says that the the Tableau corresponds to a correct uh computation of the machine um so why don't we just do the same thing okay so why don't we just build our formula using exactly the same process That we used to build a formula when we had sat being um NP complete something goes wrong we can't quite do that um the problem is that if you remember the formula that we built before was really about as big as the Tableau is because it had some
Logic for each one of the cells it had a set of some of the had variables for each one of the cells and it had some logic you know for each of those neighborhoods basically so He says that each of the cells does the right thing um so it was a pretty big formula but it was still polinomial um the problem is the Tableau is now n the K by D to the N the K that's an exponentially big object so if your formula is going to be as big as the Tableau there's no way
you can hope to produce that formula in polinomial time and that's the problem the formula is Going to be too big remember we're trying to get a polinomial Time reduction from this language a so we have an input to a you know a string that might be an a which is We simulating The Machine um and then you know uh the size of the Tableau relative to W is going to be something enormous and so if the formula is as big as the Tableau there's no way to produce that formula in polinomial time so this
is Not going to work let's try again so now we have here uh now so remember this notation from CI to CJ in B steps okay so we're going to give a general way of constructing formulas which Express this fact that I can get from uh configuration I of M to configuration J of M in B steps whatever that b is B is going to be some bound and I want to know uh can I get from this configuration to that configuration and I want to write that down as a a formula which is going
to express that fact and it'll be either true or false and I'm going to give you a recursive Construction for this formula so I'm going to build that formula um uh for a value B out of formulas uh for smaller values of B okay so this is going to be a way of constructing that formula in terms of Other formulas that I'm going to build and there's going to be a basis for the recursion when b equals 1 okay so that's the big picture so let's see how does this formula look um so let's let's
not worry about the case for b equal 1 right now this is the case for larger values of B so I'm G to the fact of that I can get from CI to CJ within B steps I'm going to write this down in the in this way uh and let's try To uh unpack that and see what it's saying um you know without worrying about how we going to carry this out let's just try to understand at a high level the semantics of this thing what is trying to say to you it's going to say
well I can get from CI to CJ in bsteps so M can get from CI to CJ and B steps if there is some other configuration C Mid I'm calling some other configur I'm calling it C Mid very much inspired by the previous proof um Savage's theorem where there was C Mid was that intermediate configuration so now instead of trying them all I'm saying does there exist one where I can get from CI to C Mid in half the number of steps and from C Mid to CJ in half the number of steps so if
I can build these two config these two formulas then I can combine them with this sort of extra stuff out here and them and them together and put an exist Quantifier says does there exist some configuration some way to findi find a configuration such that it works as these formulas require if I can do that then I'm going to be good because then I can um well good at least I'll be good in terms of making something that is going to work um so first of all let's understand what I mean by writing down uh
does there exist C Mid it's really if you you know thinking back to the way We did the cookle theorem we represented these configurations by variables which uh were indicator variables for each of the cells and we're going to do exactly the same thing so we're going to have a bunch of Boolean variables which are going to represent some configuration so more more you know formally or in more detail what this does there existence C Mid really is an assign into all of those variables that represent um the cells of the contents Of the cells
of those uh of that configuration okay so now let's see how to you know how does how will the recursion work so um to get this value here I'm going to do the recursion further so does there exist a C Mid and now um for getting from CI to C Mid can is there some other C Mid this is like another value of w from the previous slide where I'm getting again I'm cutting the number of steps in half again so I'm going from B Over two steps to B over four steps and I'm going
to do the same thing over here so I'm just uh unraveling the uh the construction of this formula in terms of um building build by building it up recursively um so um and then I'm just going to keep doing that until I get down to the case where b equals 1 um and when if I'm now trying to make a formula that's going to be say I can Get from CI to CJ in just a single step so this is really talking about a tableau of height one or height two then I can just uh
directly write that down the way I now the Tableau is not very big so now I can write that down using the neighborhoods and so on that I did in the cookle theorem proof um and this is how you put it all together um and now if you want to talk about the Um uh getting from does does m accept W so I initially say can I get from the start configuration to the accept configuration in t-steps which is the maximum running time of the machine so again you know if you followed me what happened
um in Savage's theorem it's the same it's the same uh values uh now the thing is is we have to understand how big this formula is and if you think it through Um uh if you think it through um there's a problem because what's going on here I'm expressing this formula in terms of formulas where um the size of B is cut in half but now there are two of them so it's two formulas on half the value of B that's not going to be a recursion that's going to work in our favor um so
let's just see what happens so each recursive level Uh doubles the number of formulas right going here we have two formulas here we're going to have four formulas and and so on so the number of formulas doubles each time so the length of the thing um that we're writing down is doubling in size each time we go to down the recursion that's going to be okay if we don't go too many levels but unfortunately we are going quite a few levels because the number of levels is going to be log of this initial um EXP
Itial size thing so it's going to be end the K levels and so if you're doubling something into the K times you're going to end up with an exponentially sized formula and again we failed okay so let's I have a check-in on this but I'd like maybe we should spend a couple of minutes just making trying to understand what's going on here um because the next slide is my really my last slide and it's going to Fix this problem but let's make sure we understand what the problem is before we try to fix it um
why can we no longer write over each layer of the recursion as we did in latter oh that's kind of a cool question what does it even mean to write over the different well you know uh so that that that's kind of an interesting question here so in a sense that's going to be the solution we're going to Uh um you know reuse things in a certain way but but for but I want you to understand that this method itself does not work because this recursion here where I'm writing the formula I'm building the formula
for B out of formulas for smaller values of be um if I if I do it that way I'm going to end up if I do it as it's described in this um procedure here I'm going to end up with an Exponentially big formula and that's not uh good enough so if you cut the formula in half each time even though you have two formulas won't the length be the same um I'm not cutting the formula in half I'm cutting the value of B in half so you have to say say B is initially an
exponentially Big Value so we're going to end up with an exponentially big Formula so it's not really cutting the formula in half cutting the b in half B starts out big I mean that b is this B is initially this value here D to the N to the K I'm worried not too many questions here I feeling that's that that's that's probably not a good sign uh so if you're if you're if you're well I mean if you're hopelessly confused maybe I can't fix it um quickly So anyway why don't we move on and see
how to repair this how to fix this problem um and that is going to be by a trick um in fact I know the people who were involved with coming up with this this was actually this proof was done originally at admit um and uh many years ago in the 1970s um and uh the folks who were involved with it called it the abbreviation trick so That's what we're going to do on the next slide uh oh no this is a check in first why shouldn't we be surprised that this construction fails um a well
we can't just the notion of defining a Quantified bulling formula by by using recursion is just uh not allowed so you you just can't you can't Define formulas that way doesn't use the for all quantifier anywhere or because we know that tqbf is not in P okay see what you um what what do you think why can't why should we not be surprised uh I guess I could put an could could have put a D in there not surprised because you're not you don't know what's going on that's another reason not to be surprised but
um anyway um hopefully you have some glimmer of what what's happening here and why don't we just uh almost finished so I'm going to shut This down in a second last call okay ending all right so in fact the right answer is B um I mean one should be suspicious that if you're not you know if you're not you're not there's no for alls appearing in this construction anywhere um so really what we're doing is we're constructing a formula that has only exist quantifiers so it's a Satisfiability problem so really what we just did was
we constructed a um we we did in a more complicated way the cookle construction because you end up with a sat sat formula only with exist quantifiers and so uh really try one and try two were the same so it's not surprising that you end up with an exponentially um big um formula as a result I don't know a lot of you answered we know that tqbf is in P is not in P we don't know that I don't know Where you what's happening with you guys uh uh but no uh maybe that was a
protest vote uh but anyway no we we don't know that TQ and what does that got to do with anything anyway so anyway that's Le let's let's see how we solve this um in our remaining uh few minutes here um and uh so here is the solution re he remember the this part Where we're saying we're trying to find C Mid um does there exist a C Mid such I can get from CI to C Mid and half the number of steps and c m to CJ in half the number of steps I'm expressing one
formula in terms of two formulas that's where the blowup is occurring because these two are then in turns going to each so these two going to become four become eight and that's not good can I express this fact in terms of just one Formula and it's kind of a little a little bit in the spirit of someone your suggestions can we kind of reuse things in a way and that's what we're actually kind of kind of do um so here's another way of saying the same thing but with just a single formula and it uses
a for all and the idea behind it is that a an and is kind of like a for all or a for all is kind of like an and just like an exist is kind of like an or so when you're saying does something exist you Know it's is it this thing or that thing or that thing or that thing and when you on saying for all it has this thing and that thing and that thing and that thing so ands and for alls are very much related and so we're going to convert this and
into a for all we're going to say for all configurations CG and CH that are either set to c i c mid or to C Mid CJ the formula CG c i can get from CG to CH in half the number of steps so you have to think about what this is Mean here um uh and I also want to make sure that you don't feel I'm cheating you because well first of all so now we have just a single formula we're going to go down to the case b equals 1 as we did before
you have to make sure that saying this restricted for all is is not a cheat when you have for all x's and S like we have over here is equivalent to saying for all x if x happens to be an S then the other thing follows and this Implication can be expressed using NS and ores um and as before the initial um starting point is going to be with going from C start to C accept in t-steps and so the analysis that we get is that uh because there's no longer a blowup each recursive level
just adds um this stuff here in front um the exist C Mid and the for and this for all part so that's going to be adding order n to the to the to the formula instead of Multiplying because we have two formulas um and now the total number of levels is order n to the K as before so the size is going to be n the K time n the k um uh or order into the 2K um I actually had a brief check in here um which I'd like you to do just you know
in our remaining few seconds um does this construction depend on M being deterministic um so let me just launch that uh I want you to guys to get your check in credit here um But in fact if you uh you have to think this through um we're that formula says that the Tableau you you get a tableau is that going to matter depending upon whether it's deterministic or non-deterministic it's actually um well it's a kind of running 50/50 here um why to just pick something because i' i' I'd like to just uh close this out
and just get to our last slide um so if You don't don't follow don't worry um but it's actually interesting point that um the fact that this um so I'm going to end this all in uh so in fact the right answer is um it still would work if it's if it's non deterministic and this would give you an alternative way of proving Savages theorem so really this all comes down to this proof which implies Savages theorem and then in turn implies the latter DFA problem so anyway that's side note not Critical for scanning really
you can take those as all separate results and and that's good that's good enough all right so um uh um coming back oops uh coming back this is uh this is what we did and um so each recursive level the size of the qbf is not the same somebody's asking is it the same at each recursive Level now we had to add in um uh let's just see what each recursion so you know we have this recur this is recursively built here but now we have to add this part in front and this part here
in front so the quantifier you know which is Quantified over a bunch of variables representing the configuration that gets added on at each level so it's not that it stays the same um there's stuff that's get added in but what's Important is that doesn't blow up exponentially um the Stu thatu gets added in every time but not multiplied um okay so we we're done here so anybody you can all take off I think many of you already have bye-bye thank you for
