1 00:00:24,720 --> 00:00:27,029 greetings everybody uh welcome to our last lecture of the term we have survived a a semester online in 18404 and um we are going to conclude our last topic today which is interactive proof systems that we started last time and um with the big well the um uh the big theorem of interactive proof systems is that um i p equals p space and we're going to give the main idea for that in a slightly weaker uh theorem um as we'll see so uh why don't we jump in um so today's uh we have been doing interactive proofs we gave an example of showing that the graph isomorphism problem the complement of that is an ip as you i hope you remember we had those that interaction with approver and verifier we're going to go through it quickly not that protocol but just this setup and then we're gonna uh finish uh by showing that this numbersat problem is an ip and conclude that cohen p is a subset of ip all right so let's go for it um [Music] yes um so just remember interactive proof systems there were these two parties the approver and the verifier the approver has unlimited computational ability um i kind of uh you know uh modeled that as a an army of students perhaps who are uh have who can um where we where we don't uh they can work all night they can use computational resources and um the prover however we're not gonna measure the computational power of the approver that's unlimited and so the approver can do things like find certificates it can test whether things are satisfiable it can factor numbers we don't care they can do whatever we'd like and there's no charge for the provers computational um demands okay so the setup we had was the approver and the verifier both see the input they exchange a polynomial number of messages and then the verifier accepts or rejects and we had this notion of the probability that the verifier ends up accepting when paired with a particular prover and we what we want is that for strings in a language that probability should be high for some prover and for strings not in the language that prover that probability should be low no matter what the prover does so there's nothing the prover can do um and the way it kind of suggests that any particular any prover but whatever the provers strategy um cannot make the verifier accept with high probability just doesn't have enough information or it doesn't it's just not able to make the verifier accept with high probability um i i uh you know you might think of the prover is trying to make the verifier accept so you know that pete tilda is a crooked prover i didn't i don't think that that was went down very well with everybody so i i have it here another way of looking at it maybe it looks a little bit more like np here where um ip is the collection of languages where there's a verifier just like we had you can think of np as a having a verifier which can check certificates here the prover is going to be like the certificate so that for strings in the language there's approver which can interact with the verifier and make it accept with high probability and you're not in the language there is no prover which can interact with the verifier and make the verifier accept with even more than low probability what's important is this gap just like with bpp between acceptance or rejection and that gap is there because we want to be able to use the amplification lemma and if there was no gap then you wouldn't be able to amplify and make a make the probability of acceptance extremely high when you want it to be in the language when you're in the language and extremely low when you're not in the language um okay so i hope that gives you you know refreshes your memory as to how that works we're gonna um walk ourselves through the um uh um [Music] well through that what we did last time but let's set the stage for that so the surprising theorem as i mentioned is that i p equals p space um one direction of that is a fairly standard simulation you if with p space you can basically work your way through the tree of possibilities for an interactive proof uh protocol and you can calculate the probability that the verifier would end up accepting if you had the best possible approver that would make try to make the verifier accept and you can just do that calculation it's in the book um you're not going to be responsible for knowing that actually we haven't covered it in lecture but it's not very hard um a little technical i suppose the other direction is the interesting one and that's the direction we're going to be moving toward today we won't quite get there um but the way it works is that uh to show that everything in p space which is kind of amazing um is contained with an ip so everything in p space can be done in i with an interactive proof system and the way that is done is by using a piece based complete problem tqbf and showing that that problem itself is an ip uh but we we we're not going to prove that um that would be sort of the next thing we would prove if we had a little bit more time but um we're going to be satisfied with just the somewhat weaker but very similar statement that cohenp cohen p is contained in ip here again still very surprising because you have to be able to show for example that a formula is not satisfiable with approver how can approver convince a verifier that a formula is not satisfiable um you know the showing that it is satisfiable you just give the certificate which is the satisfying assignment but how do you show something's not satisfiable it's unexpected um and the proof of that is pretty much similar slightly is one kind of technical point which we don't have to get into so it's slightly easier but very much in the same spirit so remember this number set problem is you're given a formula and a number and the that number is supposed to be exactly the number of satisfying assignments of the formula um so in particular formula is unsatisfiable then it would be paired with the number zero and that's why uh the number set problem is cohen p hard because you can easily reduce the unsatisfiable unsatisfiability to number set and unsatisfiability is uh coinp complete okay so remember we introduced this notation last time this is going to be critical for understanding this proof so let's go through it once again so if you have some formula what i like to do is preset some of the variables of that formula so that's going to be a formula on m variables x1 to xm and i'd like to preset the first i variables to certain to zeros or ones as i wish um so i'm going to indicate that by fee with 0 means i'm setting x1 to 0 and the rest of the variables remain variables um and more generally fee of five i values a one to a i which are going to to start off with are going to be just zeros and ones just boolean values that's going to be the formula with those first x1 to set to a1 dot dot x i set to ai for those i constants um which are zeros and ones um i'm going to call those presets because we're presetting some of the values of the some of the variables in the formula and the rest of the variables we're going to leave as variables so we get a new formula on fewer variables by doing this pre-setting process and we're going to get to do the same thing in terms of counting the number of satisfying assignments so remember the notation number fee is the number of satisfying assignments number fee with a preset of zero is the number of satisfying assignments when you've set x1 to zero and number fee of a1 to ai is where you set the first i variables to those i values and then you're going to look at the number of satisfying assignments with those presets in mind okay so there were two facts i'm going to call them identities because we're going to um rely on those and we're going to actually extend those to the non-boolean case as we'll see shortly so um these two identities say that um uh first of all if i preset i i think the understanding the first one is clear just by thinking about it in the case where i equals zero so this is the case where the number of satisfying assignments altogether is the number of satisfying assignments when i've set x1 to 0 plus the number of satisfying assignments when i've set x1 to 1. and this just generalizes that when i look at having already preset the first i variables so if i preset the first i variables to these i values that the number of satisfying assignments i get there is the number of satisfying assignments i get with those presets plus the next variable being set either to zero or to one and then you add those up the same idea and lastly if i set all of the variables to values so i have no variables left and i look at the number of satisfying assignments consistent with that fully set um variables so there's no variables left everything is set everything is preset that's just whether or not those values have satisfied the formula already or not so this is going to be equal to zero or one the number of consistent satisfying assignments with those m presets where m is the number of variables is just whether those m values satisfy the formula which case i get a one or they don't satisfy the formula in which case i get a zero okay critical to understand these in the boolean case because we're going to generalize this to the non-boolean case and it's going to be just more abstract the formulas are going to look the same but we're going to have to um kind of we're going to lose the intuition that those things correspond to satisfying assignments or counting the number of satisfying assignments all right let's have a quick check in here um so let's we're just going to do an example to hope to you know nail this in this idea so here's a particular formula fee um and now remember number fee is the number of satisfying assignments a fee the number of satisfying assignments where i've set x1 to 0 and so on okay so just and here i'm really kind of giving you two options in in each row for the value now you have to check all that are true so it's really going to be one at most one per row presumably um all right let's see how if your file if you're with me here so the number of satisfying assignments uh for uh altogether well there are two ways of satisfying this formula either um this is really like exclusive or um so either x1 is 1 x2 is 0 or x1 is 0 and x2 is 1. so one of the value variables has to be true the other one has to be false and then you're going to end up satisfying both clauses as you can easily see um so b is b is correct in the first line now if i'm going to already commit to saying the first variable is set to zero now how many satisfying assignments can there be well the second variable just has to be set to one in order to satisfy so now there's going to be only one satisfying assignment consistent with setting the first variable to zero now if i set the both variable both variables to zero now how many satisfying assignments can there be consistent with that assignment they can be zero because um if uh in order to satisfy this formula one of the variables has to be zero the other one has to be one if i'm presetting them both to zero there's not going to be any satisfying assignments because zero zero does not satisfy the formula okay apologies for messing up that uh uh checking on the last day oh well um all right let's get let let's first go over the um uh the protocol we attempted for number sat uh last week um on thursday okay so we're given the input the formula and a k and remember what we want to happen we want the verifier to end up accepting with high probability when k is the correct value and with low probability when k is the not c not the correct value um now this is going to be as you may remember from last time this is going to end up being a flawed protocol because it's exponential we're only allowed to be have a polynomial size protocol but um just looking ahead in this protocol the verifier is going to end up accepting with probability one for an honest approver and with probability zero no matter what the prover tries to do so for any prover um the probability the verifier can cannot be made to accept so this is kind of an extreme case um where there's not going to end up being any probabilities but it's an exponential protocol so in that sense it doesn't do what we need so let's go through it because it really sets us up for the polynomial protocol with the non-boolean values all right so first the prover sends um let's just look at it and not rush it the approver sends um the [Music] number of satisfying assignments according to the approver the verifier checks that is equal to k and i think it's best to understand this first with the case that the input is in the language so k is correct and we have an honest prover and then we'll understand what happens if k is not in the language and we'll see that no matter what the prover tries to do the verifier is going to end up not accepting um and again you know this is just a setup for the real protocol so this is kind of a dopey protocol you're going to think what what the world and why am i doing this um it's not uh it seems like i'm making something that's very simple complicated but it's really just the framework that i'm i'm putting together because well you'll see all right so the proof is going to send the claim for the number of satisfying assignments um which in the honest case is going to be the correct value the verifier checks that it matches the input now the verifier says well i want to be convinced that your claim is correct so the approver is going to justify that claim by saying well the total number of satisfying assignments is whatever it is a hundred because the number when i have x1 set to zero um is 60 and the number when i have x1 set to 1 is 40. and that adds up to 100 which is what you would need to have happen so the verifier checks that the sum is correct and then says well now how do i know those two values are right so then the approver unpacks it one level further so breaks those two down by uh justifying that fee 0 was correct that value 60 was correct by saying well now if i set the next variable x2 to 0 and 1 that's going to have to add up to v0 so maybe to get 60 i had you know 50 and 10. and to get 40 for the number fee of one i had 20 and 20. so these these i have to add up um so each level justifies the preceding level that's gonna we're gonna have that happen again um now the prover says well i mean i still don't you know i need to be convinced you know i don't trust you i need to be convinced that these values are correct um so uh level by level the prover is going to be setting more and more of the variables in all the possible ways until it gets down to the very bottom where it's setting the variables to in all possible ways so exponentially many settings here um and the verifier now checks that the previous round was correct so that's where we set only the first m minus one the very last variable hadn't yet been set um so it checks all of those two to the m minus one possible settings um in terms of the new settings that it got where we set those m minus one settings but we extended it by zero and by one and this is that same identity that we used from before um and now now that the proofer has sent all of those possible values rever the verifier needs to be sure that those are still correct but the the thing is is that at this point to verify those are all zeros and ones because they all say whether that assignment satisfies the formula or doesn't satisfy the formula so the verifier can check those directly checks each of those whether just by plugging into the formula and seeing did does it satisfy the formula or not so each one of these is a zero one value which corresponds supposed to correspond to whether the formula was satisfied or not those all are correct um uh and everything else along the way has been correct the verifier is going to accept otherwise if at any point the ver one of those checks failed the verifier is already rejected or at this point it just rejects okay so that is the um the protocol the exponential protocol um and i'd like i i you know not sure if this is helpful to you or not but i like to think of it sort of as a tree of possibilities um so uh these yellow values are what the prover is sending so the approver first sends the number of satisfying assignments all together the verifier in white is checking uh is that are they doing these checks so it checks that it equals k and then the prover sends the next level the verifier checks that the edition works out then the approver sends unpacks it further assigns values to the first two variables and the verifier checks that just the assignments to just a single variable are consistent with that and so on and uh total set assigned all m variables and then it checks directly with the formula now what happens and here is the case it's going to be important to understand both in both here and in the non-boolean case what happens if we had an incorrect value for the input and what i want to show you is that the prover is going to you know i want to show you that the verifier is going to end up rejecting in this case um with certainty later on it's just going to reject with high probability but for this protocol it's going to accept with certainty um and why is that because uh first of all if if the prover if if k was wrong so i'm indicating the wrong value is in red if if if k was wrong so it did not equal the number of satisfying assignments if the approver sends the correct value the premier is just going to be going to say it doesn't match up i reject right away so what is what can the proverb possibly do to prevent the verifier from accepting you're going to see that there's nothing it can do but later on there's a chance that the proverb can get lucky but here there's nothing you can do let's say let's let's try to humor me and see that what let's approve prover try to manage to uh keep the verifier going as long as possible so the approver in order to prevent the verifier from ejecting at the beginning would have to lie about the number of satisfying assignments but then the approver is going to say well okay you know uh you know if you you know you're claiming there's only 99 satisfying assignments proverb doesn't know what the right real answer is but the you know the we know it was a hundred let's say but let's say you know we k was equal to 99 the approver claimed it's 99 now um and so the uh the verifier says okay well it's 99 convince me of that so now the approver is going to have to say the number satisfying assignments for zero and the number of satisfying assignments for one they have to add up at least one of those has to be wrong because you can't have the two correct values adding up to the to the lot to the to to the false value so a lie here has to yield a lie in at least one of those two places and then a lie there is going to have to yield a lie in one of those two places just like you know each lie kind of forces more lies you know as you know you're trying to lie the story gets more and more complicated in order to try to justify all this um and so in the end you're going to get an inequality and the verifier is going to end up rejecting somewhere along the line there's going to have to be an inequality if not along the way then at the very end when the verifier does the check itself because one of those if you trace that down there's going to be lies and lies and lies and then there's going to be a at the very bottom one of these values is going to be wrong and when the verifier checks them all it's going to find out that there is an inequality there and so one of those checks is going to fail okay so um uh so i'm getting one question here why is this any better than just checking all possible assignments without approval you know i yeah it isn't the only reason i'm doing this is to get us ready for the um arithmetized product protocol where we have non-boolean values coming in okay so with questions on this i think it's important to um understand this one don't understand don't ask the question why the why is just going to be we are getting ourselves ready for something later which you don't haven't you don't know yet but i just unders i want you to understand it for what it is even if it seems unnecessarily complicated okay so let's keep going so how we're going to fix that protocol so it's not exponential so again here is a picture of that exponential protocol and you know we have that exponential blow up occurring because at every stage each value is going to be justified in terms of two values at the next stage so it's going to be an exponential exponentially many values after a while so instead we're going to try to justify each value here in terms of just a single value at the next stage but you know it's not going to be good enough just to pick either the zero or the one at random um because it might be each there might be just a single course of lies um going through here and the only way to k would you you would be to catch that would be to guess correctly at each stage which was which was the lie and then you would catch it at the end um if you're just going to be randomly picking zeros and ones um you're not going to have a high probability of catching the prover when it's uh when it's lying and so um that's not going to be good enough you you want you know the the input might be the wrong value and you might have approver which is just has one path of lies um and then your probability you would still have a high probability of accepting in that case even though the input was wrong that's not what you want for the when you have the the input is wrong you have to have only a tiny chance a very small chance of accepting um so the way we're going to achieve that is by having these instead of picking a zero or one for the values of uh for these random values we're going to have non-boolean assignments to the variables and we have to make sense of that and we've already seen an example of that it's going to be very much the same um all right we are we on all we are are we all together here so this is a a place where we could try um uh if you have a question we can try to um answer that um are we good let's keep moving okay so how we going to arithmetize boolean formulas it's again the same idea we had before simulating hands and orders with plus and times so we had this from before same exact picture actually it's even simpler because now we're going to be using the true simulation of or instead of some kind of a special case simulation of war in terms of which we had in the branching program case so these faithfully do what and and or does when you plug in zero for false and one for true so that means that we can take an entire formula and arithmetize it the formula built out of ands and ors and negations and you're going to get a polynomial that comes out um and that polynomial what's going to be important for us is not going to be of extremely high degree the actual degree is going to be at most the length of the formula in terms of the number of symbols it has you can check that on your own you can but for now you can just trust me the degree of the polynomial because it only goes up during the um goes up during the multiplications but the the degree doesn't become too big um uh okay so and we're going to be doing and i don't want this to be a confusing issue here we're going to be doing but you know we have to be correct um i don't want to be cheating here so all of the arithmetic is going to be done in a field so um we have to uh do plus and times mod some uh number which is gonna turns out needs to be a prime number for reasons i'm not gonna get into um but it doesn't really matter it's just modular arithmetic and that's one thing that enables us to pick random values in a natural way because there's only finitely very many values in the field and so you're just going to pick one at random but here we want to be able to represent we it's it's going to be more important for us to have a larger field because we want to be able to represent in the number of satisfying assignments which can be a number between 0 and 2 to the m so we have to have a field which has at least 2 to the m elements in it so that we we can in a sensible way write down those numbers um let's not get caught up with that but um we can try to answer those questions offline if you want um but just think about it for this first pass we're doing the arithmetic mod sum prime okay so now we have the same notion as of presets as we had before so if we have a formula and we preset some of the values but now those values may be non-boolean values we may be setting plugging in values for the formula not just zeros and ones but we might be plugging in sevens or 20 23s or whatever and you know the formula is gonna you know in order to have a value a meaning to that we're gonna treat that formula as the polynomial from the arithmetization and just plug in those values into the polynomial and see what the polynomial does for you so here we're going to be presetting some of the values of the formula like we did before and he now we're going to it's going to be the same thing but now in the polynomial we're going to be pre-assigning some of the values of the variables to these a's which from the field and the remaining variables are going to stay as unset um now we have to give an interpretation now he is um so the new polynomial here okay so i'm getting a question well maybe i better take this let me just let me hold off on that for now uh what the uh degree is um um okay i'll come i'll answer the questions in a second so so now remember from before number fee was the number of satisfying assignments when i preset the first i values it no longer makes sense to talk about satisfying assignments because these values may no longer be booleans so i'm going to have to write this formally um as i'm going to plug in those values those i values for the first i variables and the remaining variables which i have not set i'm going to assign them to zeros and ones in all possible ways only to zeros and ones because what i want to have you know you might think well why you know why not we why aren't we assigning these to other values in the field well because what i'm aiming at is that if i were to plug in zeros and ones at this point into the polynomial i'm supposed to get exactly the same values as i had before because i'm simulating ands and ors so i'm just extending the um the definition the the the the evaluation into a new realm but i shouldn't change the values on the old boolean realm so i'm going to be adding up the unassigned the unset variables in all possible boolean ways and the first i values could be non-boolean values okay so you have to just to accept this as an abstract notion um no longer has an interpretation as satisfying assignments okay so as i said what's important is that for if i if i happen to put boolean values in now then uh fee and number fee get give the same values as they would have before because the polynomial acts identically to the formula on boolean values okay so this is what i'm repeating what i said and there's another point that isn't that's also you know you have to check which is that the identities that we had earlier that connected up what happens when i set the first i values and and i set the first i plus 1 values those still hold so if i set the first i values now to possibly non-boolean some non-boolean assignment that's what i get when i extend those values um to one more a variable being assigned but i just need to assign that variable to zero and to one and add those up because of the way i've defined things over here so i've uh assigned those variables you know i i to zeros the unset variables to zeros and ones you know when i'm defining the um the number fee uh function okay so and then lastly when i assign everything now to possibly non-boolean val values that's going to be there's no longer anything to add up so i'm going to get exactly the same as i got from before when i so assigning number fee of totally preset input it's the same as fee with a totally preset input okay because in that case there are no variables left to add up over so uh there's just one just i just get one single uh my sum has just one element in it okay um so uh i'm getting i got a question here for earlier what happened to the degrees of the polynomials uh well the degree of number fee is going to be at most the degree of fee because i'm just adding things up and addition doesn't change degrees um as i preset values the number of variables goes down but the degree may not necessarily go down so the question was i got is the new are the new polynomials having lower degrees not necessarily they have fewer variables but not a smaller degree okay so let's do this check it let's see if that now again this is i think i have messed up on this so uh well there's one of these that's does it i i i i'll give it away in part there's only one of them that was true anyway so you can check the one that's true according to the way we've we've defined it okay so this is a little bit of a trick question here um as i'll explain but there's only one of them that's faithfully does the arithmetization as i've described on this page and that's the one you should check okay so um remember here over here this is the formula this is the recipe for how i'm doing the arithmetization of this this whole process here so one of these lines one of these a b or c corresponds to doing that okay i'm going to close this down so are we all in yeah so a is the correct answer um a does the arithmetization according to the recipe that i just described because if you look at x1 or x2 you can just look check it in the very first um part of the uh the polynomial x1 or x2 well it's x1 plus x2 minus the product x1 x2 so you can just see it right there the others don't have that um and the similarly for x1 bar and x2 bar it becomes 1 minus x1 1 minus x2 and then the product of those so a is pretty straightforward as the arithmetization of phi now in fact any of those would would work i don't want to confuse you here but any of those would have worked because they all agree on the boolean assignment and that's all that really matters um so if you have any all i care about is that they agree the formula agrees with the polynomial in the boolean cases and these all happen to agree on zeros and ones not doesn't matter though uh i put those there just in case you you tried it by just substitution of zeros and ones in you might you might have picked the wrong thing um okay so let's uh let's take a break here and then we will um see about how to go about fixing the protocol um after the break uh all right so now also happy to take any questions we haven't really done a whole lot we basically this has all been review um of what we did last time um but um let me start the uh timer um and then uh but feel free to ask questions it's the setup is i'll tell you where we're going this whole proof really comes down to understanding one line which is going to be in the second half um so i'm really kind of this is all big set up here to get you ready to be able to understand that one i'll tell you when it's coming so you know you won't you won't have to uh worry that you'll miss it but it's a that line is is not easy to understand so i think it's important to get all of the framework and all of the um uh the context all set up for you so then you can understand that line and and hopefully you know you see that line and understand it okay so uh the important fact um okay so let's go back you wanted to see the important fact um uh [Music] okay um so this is what i was saying before the if i plug in boolean values into the arithmetization i get the same exact thing as i would have if i applied the boolean operations before i did the arithmetization so plus and times in the arithmetization give a faithful simulation of and and or according to these uh little formulas that's that's all i'm saying with this and so if i plug in boolean values for the a's um [Music] i get exactly the same as i would have gotten before i did the arithmetization because the arithmetization is a faithful simulation i'm should i also say it let's see um what does the or rule now why does the or rule now contain the minus a b term while the previous instance of arithmetization didn't because why remember in the case of branching programs we didn't need the minus a b term um over here and that was because we could argue that it was a disjoint or um in the case of the branching programs i don't want to get confusing by trying to explain why that was but in that earlier case we never had took an or of two ones it was an or of zero zero possibly zero one or possibly one zero and so therefore we never had to deal with the case when we had an or of a one one and here we can have that so we have to subtract off that a b term because otherwise we'd have if we just had a plus b then when the one one case we would end up with a two and that would not be a faithful stimulation of the or operation because one or one should be just one not two so a good this is a good question here do all the numbers need to be zeros and ones i'm not sure how negation would work would work with larger numbers so this is um the negation is just you just blindly follow it even though we're going to be plugging in non-boolean values um [Music] you know it's gonna be one minus a seven so you're gonna get minus six you have to do that mod p so whatever mod q so whatever whatever that value you get but um you can no longer think about it as negation in the in the in the former sense now it just becomes a formal thing um you're you're just plugging along doing what the polynomial says numbers are coming out you think you know this is just nonsense but the thing is it's going to have a meaning that's going to be useful to us that's that's what this protocol is going to show yeah so um you can't think about it as negation anymore it's just the negation becomes one minus x in the power in the arithmetized world and you just have to live with that let's see um okay uh another question here if all the fee are equivalent for boolean inputs in the in the check-in um so this is back into this check-in here so if all of the uh p yeah you know so the question is why if they're all equivalent in the boolean case uh why is only a correct um because this is i define piece of fee in a particular way and so this was the value you got if you follow the way i define piece of piece of fee the others would work they just weren't the way i defined it um okay uh any other questions here we should probably move on okay can arithmetization be used in other contexts um uh i often i don't know i there are these two cases where arithmetization works whether there are other cases too i'm actually not sure okay so let's move on so uh our our but our timer is up the candle is burned down okay so this was um okay here we go this is the real protocol um so i'm going to present it to you the way i did before let's think about it with the case first where the input is in the language and we have an honest brewer um so we start off the same way the approver sends fee it sends number fee which in the old sense was the number of satisfying assignments it actually still is because you know since we're not presetting anything there's no non-booleans um in the picture yet so this is going to be the same value as before the verifier checks that k equals number phase so you have to that's why we have to have the big enough field there so that we can um represent numbers up to the number of potential numbers satisfying assignments but that's a side note so but anyway p sends this is exactly what we did before no change the number of satisfying assignments feel like now let's just see let's remember and this is this is one of those cases where not having a big blackboard is hampers us so i'm just going to remind you what we did last time but i'm going to change this so remember before p said sent an unpacked at one level sent the number of satisfying assignments said number uh fee of zero a number fee of one and then v did that check to justify the previous value which the verifier doesn't necessarily trust okay fasten your seat belts everybody this is the whole proof in the next line okay so but it's a doozy um all right is going to send phi of z as a polynomial in z it's going to send just a single object but that object is an entire polynomial and the way it's going to send that is by sending the coefficients of that polynomial okay so let's uh let's um that statement um so first of all um let's understand the value of doing that so if i can send the entire polynomial fee sub z represent that as a polynomial i can plug in 0 and 1 into that polynomial and allow me allow the verifier to do the check that it needs to do to con to um demonstrate that uh number fee is correct so it's going to check that number fee is a number fee of zero plus number fee of one but instead of getting those values directly from the prover it's going to get take that polynomial it got and evaluate that polynomial at zero and one okay so let and just to remember let's go back and remember how we defined uh defined uh number fee to make sure that we understand what it means to have a polynomial here so remember here we're just taking the very first value you could put you are okay with putting a constant 0 or 1 and then adding up over all possible ex extensions all possible boolean extensions to that um and maybe it's okay to put in a non-boolean value here like seven and now you take the remaining variables and it and assign them zeros and ones and all possibilities and add it up now i'm going to do something even a little wilder i'm going to put in a variable for a1 some you know symbolic if you want symbolic value so i'm going to put in a value z for a1 so now i plug in z for a1 here and a2 through am are going to be zeros and ones in all possible ways so i just get a polynomial in z the other variables have been get assigned and added up over the various boolean assignments and now i get some polynomial so i get some expression in z that's just going to be a single variable polynomial okay you whose degree is it going to be at most the degree of number fee so it's degree is not going to be too big um so it sends the coefficient so the degree of that is not too big so there are not too many coefficients to send um so the coefficients are in terms of the xi's no i'm not sure what the mean the coefficients are not in terms the x i's are gone at this point the x i's we've added up the x i's being assigned to zeros and ones in all possible ways so there are no other variables left there's only z um so i'm gonna do the same protocol in a more pictorial way in a minute um so you're gonna see this whole thing twice uh but try to get it you'll have two chances to get this try to get it you know try hard each time um so it's got sensi as a polynomial in z now that's going to be enough for me to figure out which number fee of zero and number fee is of one is because i plug it in for zero and one for for z but now i can figure out what number fee of two is also because i can plug two in for z or number fee of seven i plug seven in for z okay so let's stop here and let's see on other other questions so the so is the size of number fee i don't understand the so this question about the size of number fee um is it is it 2 to the n no it's not 2 to the m because the degree of that polynomial uh number phi of z i mean you know it's a very large expression if you want to initially you know yes writing that it's going to be an exponentially big sum but the prover adds it all up for you and you're just going to have at most a small number of coefficients because the polynomial is only of a certain degree and a polynomial in one variable of degree d has the most d or d plus one coefficients to worry about so it's not that many coefficients as an expression so um shouldn't the summation take 2 to the m time i'm not caring about the prover's time the prover has a lot of work to do but the prover prov sends fee of z so uh the prover yes the proofer has a an exponential job i don't care the verifier always needs to be able to check it in polynomial time and that checking is gonna well we'll have to see how does the verifier know that that polynomial was right that's a question you may maybe you should be asking um yeah okay i'm getting lots of questions about how much time the prover needs to take yeah the proof is going to have to spend exponential time to figure out that polynomial but that's all right we're not we don't care about the provers time um yeah so the summation here is going to be adding up polynomials that is correct i'm happy to spend time because really here this is the whole proof you have to understand well we have to understand why this works but um we kind of understand half of it because knowing that polynomial is enough to you know if you could certify that that was the correct polynomial for a number fee of z then we can use that polynomial to to confirm the previous value what number fee was because you just plug in zeros and ones for this for z and you add it up but now how are we going to justify that the polynomial is correct because this looks like even a worse job now we have a whole bunch of coefficients and have to make sure all of those coefficients are right and so instead of just two values now we have like d values where d is the degree of that polynomial which could be at most like the length of the formula um uh so here is the next idea um so the prover needs to show that phi of z is correct okay um the way it's going to do that let's say so even before before we do that so fee of z is going to be some polynomial um now the prover may be lying maybe sending the wrong polynomial how does the prover convince the verifier that the power that that polynomial is the right polynomial well that seems like a tough job so what it's going to do is remember that the um there is so there you know there is there is a correct polynomial that you would get by plugging into this expression for the for the correct value so there's some correct polynomial the prover may be sending some some incorrect polynomial but now those so now we have the correct polynomial and the possibly incorrect polynomial which and the point is those two can only agree in a small number of places by that fact that we proved a couple of lectures back regarding polynomials so two different polynomials can agree only rarely so what we're going to do the way the prover is going to justify that this polynomial was the correct one is by evaluating it at a random place and then demonstrating that that value you get is a correct value if the polynomial was the wrong polynomial then evaluating it at a random place is probably going to disagree with the correct polynomial at that place because they can only agree rarely so the prover is going to demonstrate that by evaluating that polynomial at a random place that value you get is going to be the correct value and it's going to continue to do that in the way using the same protocol as we'll see so that's where we're going so to in order to show that figure z is correct the verifier now gets to pick a random value in the field and the prover is going to show that evaluating that polynomial at r1 is correct remember this looks a lot like what we had from before where we were val showing that number fee of zero is correct the number fee of one is correct now we're trying to show that number fee of r1 this random value from the field is correct so the way we're going to do that is now by unpacking it one level down we're going to be using those identity that identity by because this value here is going to be equal to um number fee of r1 comma 0 plus number fee of r1 comma 1. so the way but we don't want to send both of those so we're going to send them combined into a polynomial of number fee of r1 of z as a polynomial in z this is the new polynomial in z okay so now if you understood the previous line then hopefully this one won't be too hard to swallow because now we're going to check um the identity but here by evaluating the polynomial again but one level at the next level okay so this is this is um uh perhaps a good place to uh to take questions because this is this is the heart this is really what i spent all the time setting things up for so that you would be ready to get this thing hopefully without you know and hopefully get be able to appreciate it and understand okay so um so let's let i'm not getting questions let's let's move on a little further so now in order so the pollen again the approver has sent this polynomial at the next in stage two um now we the verifier needs to be sure that that polynomial is correct so it's going to evaluate um that polynomial that new polynomial um at a random location um so by picking a random value r2 in in um in the field uh and now it needs to show that this value is is correct um because if that polynomial had been the wrong polynomial it disagreed with the correct polynomial almost everywhere and by picking a random place it's probably not going to be the right value and we'd s all of the values have been picked and so we have one last value um uh to to select a zero and one this corresponds to the nth you know if you it would be great if i could put both pictures on um on your screen but i can't um so this very much corresponds to what happened in the exponential protocol but just along you know sort of this arithmetic arithmetized one single path so uh it checks that the previous value is is correct in terms of expanding it with zero and one but again the zero and one comes from evaluating the polynomial um and now the verifier needs to be convinced that that polynomial was right so it picks a random value but now it doesn't rely on the prover anymore it's going to see whether that that assignment that it gets by evaluating the polynomial with that random value rm plugged in is the same as what i get by evaluating the polynomial for the formula itself that the verifier can do directly because this is now a polynomial now just plugging into the formula and using the arithmetization to get a value out okay so this was the last line of the identity okay we had those two identity those two identities so this is the second identity and we have to check that this is correct okay so uh so i'm gonna describe show this to you in a picture uh not sure it'll help if you're if you're confused but why don't we take some questions on this so as i said i'm going to give you two chances to understand this um because i know it's tough this is especially with the constraints of zoom this is a particularly challenging idea to explain okay so let's see so the benefit of this approach is that the approver only sends one item for each depth level instead of multiple items that's right but that one item is the polynomial so that that captures all of the values for the entire field but taking advantage of the arithmetization that one polynomial you know us has a lot of information in it and what's nice is that you can check that polynomial by just evaluating it at random one random place you can check that that polynomial is correct um okay um so where does so i'm getting another question here where does this come from here if we we checks that this here so this where does this so you have to look to understand why where this is coming from you have to we're at the end round now so you have to look back like at round two v has to check that fee of r1 which comes from the end of the first round so this checks that this fee of r1 is correct because that was where that was how we justified the polynomial with just a single variable the the very first polynomial is correct you know a little hard to say but this comes from the previous round this this guy here um okay so this is the polynomial for the current round this is the value from the previous round all right more questions so so why doesn't this run for exponential time another question i'm getting doesn't v need to check twice at each layer yes if the the verifier needs to check um gets two values but those two values come from the one polynomial so there's no blow up anymore you know those two values maybe you'll see it in the picture that i'm going to show so maybe just hold that question and maybe this will become clearer in the in the diagram so another question does this work because the polynomial encodes kind of encodes all the possible values together i think that's sort of true that sort of mixes them all together into one object then you have to check that one object which can be done with a sort of random probing of it um okay so so this is another good question that we'll see explained in the next slide so uh so similarly in attempt one the prover can keep lying by by picking polynomials um in rounds one you know by continuing to pick polynomials by lying about the polynomials but eventually it's going to get caught because this value is going to be the wrong value you know if the polynomial in the previous stage and the m minus f you know if it's a polynomial that the prover sent in the m state is the wrong polynomial then you evaluate it you're going to get the wrong value probably um and so then that wrong value is not going to match the correct value which is you can read you off yourself by reading the formula okay i think we should need to move on to the next slide um all right so same proof version two but looks different um again the input is that here's what the approver sends here is what the verifier sends i'm gonna i sort of whimsically designed this as a uh as a telephone chat where they're sending each method messages through uh messaging okay so the prover sends uh the number fee to start off with and then off on the side these are the checks that the verifier is going to be doing so here in our first round of the chat the approver is going to send fee of z remember this is just a a polynomial in not too many coefficients so it's a polynomial in one variable the degree is small so there are not too many coefficients here you know so this is uh so pretending this is what it might look like and then the verify so from that polynomial the verifier can plug in zero and one and see that the adds up um now the verifier to check that this polynomial is correct it picks a random value to evaluate this polynomial on um uh and so now it's going to have to check that this is correct so this is not nothing to check you're just writing this down in anticipation of the next check now the prover to justify that that this value is right that that this polynomial is right so we evaluate okay doesn't say that to prove in order to check that this value is right is going to send the polynomial for the next level um now we can from that we can plug in zero and one for z see if that adds up and now to be sure that this polynomial is right um we evaluate it at a random place calculate that value and then um uh have to have to see that this value is correct so now we expanded one level down further we pick a we we take a polynomial for the next variable and we see that it adds up okay i i'm not i'm not sure what whether this is helping or not um but we keep doing that until we get to the very last round uh where the prover's sending a polynomial make sure that this adds up correctly um and the verifier to be see that this polynomial is right picks a random value and uh evaluates it and now checks that this agrees with the formula because we've now assigned all of the variables and the then we can then we can check this number fee directly in terms of the fee um because they have to agree okay and so the verify would accept if everything checks out let's see what happens so this answer will answer some questions um why don't i go walk through what happens if um the input was wrong and we'll we'll see how the verifier is likely to catch the approver but not guaranteed to catch the approver in this case um so if k was correct the verifier will accept with the honest prover but if k was wrong so i'm going to again indicate the wrong values in red um i'm going to show you that the verifiers is almost certainly going to accept but not guaranteed so uh did i say that wrong so if k is wrong the verifier is going to probably reject but it's not guaranteed to reject so um first of all if the does not lie does not send the wrong value for a number fee the verifier is certainly going to reject because it's not going to be get any quality there um so the prover has to lie you know say you know um you know if k was 99 but the real value was 100 the approver if it says 100 the verifier is going to reject immediately so the verifies you know the proof is going to say well let's let's see what what the approver can do to make the verifier uh hopefully accept from the approver's standpoint so the proof is going to send 99. well the verifier says okay 99 fine uh convince me so the program now um you know one of these two has is going to be wrong uh has to be because the two correct values can't add up to the wrong value so one of these is wrong so that means the prover had to send the wrong polynomial because the correct polynomial would evaluate the correct answers here so the prover had to send the wrong polynomial so now when we evaluate it at a random place chances are this is going to be the wrong this is not going to be the same value that the correct polynomial would have given you the prover could get lucky we could have verified it might have just happened to pick a place with a correct polynomial and the incorrect polynomial agree and that place the approval think huh i'm saved now i can act like the honest prover from this point on and you know the verifier will never catch me you know i said a little bit analogous to the situation maybe you know you know i'm trying to see if you really studied the whole course so i'm giving you an exam but by picking sort of random places there but maybe you just studied you know a few facts from the from the course you might get lucky i might happen to ask just about those facts and then you give the appearance of having studied everything but you really didn't so here the approver might send the wrong polynomial but the verifier just queries that at the place where it happens to agree with the correct polynomial and the verb just gets lucky and the verifier is going to accept in that case but there are very few of those so that's why the prover is almost certainly to be caught if it tries to lie but not guaranteed um so again so just tracing this down uh if this was a lie then one of those two has to be a lie so therefore the next polynomial has to be a lie and so we continue so then the next value is almost certainly going to be a lie not guaranteed and so then one of those two values has to be a lot at least one has to be a lie therefore the polynomial has to be a lie and so on um uh until uh you know unless the approver got lucky along the way somewhere which is very unlikely even though it has several opportunities you know we've arranged ranges so that the chance of getting lucky is tiny at each stage so even though he has a few chances there's still going to be a tiny chance that you're going to get lucky somewhere and so this is wrong then chances are that's wrong and so therefore this is going to be a disagreement and the verifier at that point when it doesn't agree it's going to reject unless the people got lucky somewhere along the way which is unlikely okay so uh i don't know if you had so that's my all i was going to say about this proof uh i don't know if you had any questions on it but let's just see okay so [Music] uh do we have any questions i can answer how the approver gets how how does approver get number how does the prover get number fee of z um so you have to you know why is number fee of z have no other variables you have to go back and look at the the definition of number fee of number fee of a because you add up over all the other variables so now we're pick plugging in instead of a plugging a variable for that but you're still adding up over the other variables so this is a very column this is a function in just one variable which is about who can because it's you know it was original original thing was a polynomial so so this is also going to be following um i think we're starting to run low on time so this is our very last check-in for the semester here so of course there's one natural question to ask you all and for our very last check-in as we're in our last couple of minutes of the course or the least of the lectures does p equal np what do you think will maybe pb equal np be solved by a deep learning algorithm or maybe we'll never prove it give me your best guess okay we're kind of running out of time so let's not think too hard here um another five seconds all right ending polling uh i'll share that with you oh yeah i did share uh so what what do we get d here we will prove it in somewhere between 20 and 100 years from now that's the seems to be the majority opinion uh i don't know i hope it'll be sooner than that because i'd like to see the answer but uh we don't know uh uh yeah if you can prove peter from np yeah yeah i'll give you an a plus you won't have to take the final but you better be sure you're right um all right so what that is our quick review we finished number sat in ip and therefore that co-np is a subset of ip um if you're interested in further pursuit of this material i got a couple of questions on that these are some courses you may want to look at um i know i checked with um ryan williams he's planning to teach advanced complexity uh fall 2021 so um uh that's we're going to be one the most natural follow-on subject to this one is the crypto classes also are kind of make use of some of the same ideas and there's of course also randomness computation that ronit rubenfeld teaches i don't know if i didn't check with her i don't sure the next time she's going to be teaching that um and uh good luck on the final and best wishes so um and i'm gonna have office hours so if you have any questions uh you know happy to uh answer those but otherwise see you all good luck thank you for the comments yeah i enjoyed having you all as students it was it was uh it was a fun time a lot of work but it was a fun time i've always been intrigued by p the p versus np problem and i proved a kind of a i proved the exponential complexity of computing the parity function in a certain weak model of computation so parity function is very obviously very trivial function um but the for the parity function if you can't count whatever that means but there's a there is a model you can kind of set up but you can't count then parity requires exponential complexity and surprisingly not easy to prove uh but that's probably the theorem that i'm most known for anyway but that would be a topic for another day um another question why not include my hills the my hill and the road theorem seems i don't know that's a theorem about finite automata and all of those ways of characterizing the regular languages that seems kind of a tactic technical theorem i don't don't see much point in covering it and another question that some of my colleagues ask me is why don't i have rice's theorem which is sort of provides a kind of a machine for proving undecidability and uh i don't know i think that you can use rice's theorem without understanding how to prove undecidability it becomes sort of uh it's like a it's like checking off checking off a box checking some boxes and then you get conclude something's undecidable i'd rather have somebody understand it rather than just be able to use some powerful tool um can we understand that proof of the num the proof about the parity function uh that i just alluded to that's super hard you can with the knowledge from this class i think you can um the the that theorem uh relies on a certain technique which we didn't cover uh called the probabilistic method which is a kind of an amazing method uh not hard to explain but basically you show that something exists by showing that the probability that a random object has the property you're looking for is more than zero um and so therefore the thing that you're looking for that has that property has to exist um there are lots of examples of that these days but it's it's kind of an amazing method so use that method do i think quantum computing can solve useful problems beyond the capability of classical computers i have no idea whether one can really build a quantum computer it seems to be always 20 years off at least to doing one that factors and i've been literally uh i remember people 20 years ago saying it's 20 years off so uh i don't think it's converging um i i'm skeptical that they'll ever build a chronic computer that can factor i'll go out on a limb and say that but that's controversial um and whether it can solve other useful problems i'm not sure whether useful problems are there well i guess they're simulating quantum systems so maybe that that might be possible um all right i think i'm gonna i'm gonna end this now but thank you everybody take care bye you 2 00:00:27,029 --> 00:00:27,039 greetings everybody uh welcome to our last lecture of the term we have survived a a semester online in 18404 and um we are going to conclude our last topic today which is interactive proof systems that we started last time and um with the big well the um uh the big theorem of interactive proof systems is that um i p equals p space and we're going to give the main idea for that in a slightly weaker uh theorem um as we'll see so uh why don't we jump in um so today's uh we have been doing interactive proofs we gave an example of showing that the graph isomorphism problem the complement of that is an ip as you i hope you remember we had those that interaction with approver and verifier we're going to go through it quickly not that protocol but just this setup and then we're gonna uh finish uh by showing that this numbersat problem is an ip and conclude that cohen p is a subset of ip all right so let's go for it um [Music] yes um so just remember interactive proof systems there were these two parties the approver and the verifier the approver has unlimited computational ability um i kind of uh you know uh modeled that as a an army of students perhaps who are uh have who can um where we where we don't uh they can work all night they can use computational resources and um the prover however we're not gonna measure the computational power of the approver that's unlimited and so the approver can do things like find certificates it can test whether things are satisfiable it can factor numbers we don't care they can do whatever we'd like and there's no charge for the provers computational um demands okay so the setup we had was the approver and the verifier both see the input they exchange a polynomial number of messages and then the verifier accepts or rejects and we had this notion of the probability that the verifier ends up accepting when paired with a particular prover and we what we want is that for strings in a language that probability should be high for some prover and for strings not in the language that prover that probability should be low no matter what the prover does so there's nothing the prover can do um and the way it kind of suggests that any particular any prover but whatever the provers strategy um cannot make the verifier accept with high probability just doesn't have enough information or it doesn't it's just not able to make the verifier accept with high probability um i i uh you know you might think of the prover is trying to make the verifier accept so you know that pete tilda is a crooked prover i didn't i don't think that that was went down very well with everybody so i i have it here another way of looking at it maybe it looks a little bit more like np here where um ip is the collection of languages where there's a verifier just like we had you can think of np as a having a verifier which can check certificates here the prover is going to be like the certificate so that for strings in the language there's approver which can interact with the verifier and make it accept with high probability and you're not in the language there is no prover which can interact with the verifier and make the verifier accept with even more than low probability what's important is this gap just like with bpp between acceptance or rejection and that gap is there because we want to be able to use the amplification lemma and if there was no gap then you wouldn't be able to amplify and make a make the probability of acceptance extremely high when you want it to be in the language when you're in the language and extremely low when you're not in the language um okay so i hope that gives you you know refreshes your memory as to how that works we're gonna um walk ourselves through the um uh um [Music] well through that what we did last time but let's set the stage for that so the surprising theorem as i mentioned is that i p equals p space um one direction of that is a fairly standard simulation you if with p space you can basically work your way through the tree of possibilities for an interactive proof uh protocol and you can calculate the probability that the verifier would end up accepting if you had the best possible approver that would make try to make the verifier accept and you can just do that calculation it's in the book um you're not going to be responsible for knowing that actually we haven't covered it in lecture but it's not very hard um a little technical i suppose the other direction is the interesting one and that's the direction we're going to be moving toward today we won't quite get there um but the way it works is that uh to show that everything in p space which is kind of amazing um is contained with an ip so everything in p space can be done in i with an interactive proof system and the way that is done is by using a piece based complete problem tqbf and showing that that problem itself is an ip uh but we we we're not going to prove that um that would be sort of the next thing we would prove if we had a little bit more time but um we're going to be satisfied with just the somewhat weaker but very similar statement that cohenp cohen p is contained in ip here again still very surprising because you have to be able to show for example that a formula is not satisfiable with approver how can approver convince a verifier that a formula is not satisfiable um you know the showing that it is satisfiable you just give the certificate which is the satisfying assignment but how do you show something's not satisfiable it's unexpected um and the proof of that is pretty much similar slightly is one kind of technical point which we don't have to get into so it's slightly easier but very much in the same spirit so remember this number set problem is you're given a formula and a number and the that number is supposed to be exactly the number of satisfying assignments of the formula um so in particular formula is unsatisfiable then it would be paired with the number zero and that's why uh the number set problem is cohen p hard because you can easily reduce the unsatisfiable unsatisfiability to number set and unsatisfiability is uh coinp complete okay so remember we introduced this notation last time this is going to be critical for understanding this proof so let's go through it once again so if you have some formula what i like to do is preset some of the variables of that formula so that's going to be a formula on m variables x1 to xm and i'd like to preset the first i variables to certain to zeros or ones as i wish um so i'm going to indicate that by fee with 0 means i'm setting x1 to 0 and the rest of the variables remain variables um and more generally fee of five i values a one to a i which are going to to start off with are going to be just zeros and ones just boolean values that's going to be the formula with those first x1 to set to a1 dot dot x i set to ai for those i constants um which are zeros and ones um i'm going to call those presets because we're presetting some of the values of the some of the variables in the formula and the rest of the variables we're going to leave as variables so we get a new formula on fewer variables by doing this pre-setting process and we're going to get to do the same thing in terms of counting the number of satisfying assignments so remember the notation number fee is the number of satisfying assignments number fee with a preset of zero is the number of satisfying assignments when you've set x1 to zero and number fee of a1 to ai is where you set the first i variables to those i values and then you're going to look at the number of satisfying assignments with those presets in mind okay so there were two facts i'm going to call them identities because we're going to um rely on those and we're going to actually extend those to the non-boolean case as we'll see shortly so um these two identities say that um uh first of all if i preset i i think the understanding the first one is clear just by thinking about it in the case where i equals zero so this is the case where the number of satisfying assignments altogether is the number of satisfying assignments when i've set x1 to 0 plus the number of satisfying assignments when i've set x1 to 1. and this just generalizes that when i look at having already preset the first i variables so if i preset the first i variables to these i values that the number of satisfying assignments i get there is the number of satisfying assignments i get with those presets plus the next variable being set either to zero or to one and then you add those up the same idea and lastly if i set all of the variables to values so i have no variables left and i look at the number of satisfying assignments consistent with that fully set um variables so there's no variables left everything is set everything is preset that's just whether or not those values have satisfied the formula already or not so this is going to be equal to zero or one the number of consistent satisfying assignments with those m presets where m is the number of variables is just whether those m values satisfy the formula which case i get a one or they don't satisfy the formula in which case i get a zero okay critical to understand these in the boolean case because we're going to generalize this to the non-boolean case and it's going to be just more abstract the formulas are going to look the same but we're going to have to um kind of we're going to lose the intuition that those things correspond to satisfying assignments or counting the number of satisfying assignments all right let's have a quick check in here um so let's we're just going to do an example to hope to you know nail this in this idea so here's a particular formula fee um and now remember number fee is the number of satisfying assignments a fee the number of satisfying assignments where i've set x1 to 0 and so on okay so just and here i'm really kind of giving you two options in in each row for the value now you have to check all that are true so it's really going to be one at most one per row presumably um all right let's see how if your file if you're with me here so the number of satisfying assignments uh for uh altogether well there are two ways of satisfying this formula either um this is really like exclusive or um so either x1 is 1 x2 is 0 or x1 is 0 and x2 is 1. so one of the value variables has to be true the other one has to be false and then you're going to end up satisfying both clauses as you can easily see um so b is b is correct in the first line now if i'm going to already commit to saying the first variable is set to zero now how many satisfying assignments can there be well the second variable just has to be set to one in order to satisfy so now there's going to be only one satisfying assignment consistent with setting the first variable to zero now if i set the both variable both variables to zero now how many satisfying assignments can there be consistent with that assignment they can be zero because um if uh in order to satisfy this formula one of the variables has to be zero the other one has to be one if i'm presetting them both to zero there's not going to be any satisfying assignments because zero zero does not satisfy the formula okay apologies for messing up that uh uh checking on the last day oh well um all right let's get let let's first go over the um uh the protocol we attempted for number sat uh last week um on thursday okay so we're given the input the formula and a k and remember what we want to happen we want the verifier to end up accepting with high probability when k is the correct value and with low probability when k is the not c not the correct value um now this is going to be as you may remember from last time this is going to end up being a flawed protocol because it's exponential we're only allowed to be have a polynomial size protocol but um just looking ahead in this protocol the verifier is going to end up accepting with probability one for an honest approver and with probability zero no matter what the prover tries to do so for any prover um the probability the verifier can cannot be made to accept so this is kind of an extreme case um where there's not going to end up being any probabilities but it's an exponential protocol so in that sense it doesn't do what we need so let's go through it because it really sets us up for the polynomial protocol with the non-boolean values all right so first the prover sends um let's just look at it and not rush it the approver sends um the [Music] number of satisfying assignments according to the approver the verifier checks that is equal to k and i think it's best to understand this first with the case that the input is in the language so k is correct and we have an honest prover and then we'll understand what happens if k is not in the language and we'll see that no matter what the prover tries to do the verifier is going to end up not accepting um and again you know this is just a setup for the real protocol so this is kind of a dopey protocol you're going to think what what the world and why am i doing this um it's not uh it seems like i'm making something that's very simple complicated but it's really just the framework that i'm i'm putting together because well you'll see all right so the proof is going to send the claim for the number of satisfying assignments um which in the honest case is going to be the correct value the verifier checks that it matches the input now the verifier says well i want to be convinced that your claim is correct so the approver is going to justify that claim by saying well the total number of satisfying assignments is whatever it is a hundred because the number when i have x1 set to zero um is 60 and the number when i have x1 set to 1 is 40. and that adds up to 100 which is what you would need to have happen so the verifier checks that the sum is correct and then says well now how do i know those two values are right so then the approver unpacks it one level further so breaks those two down by uh justifying that fee 0 was correct that value 60 was correct by saying well now if i set the next variable x2 to 0 and 1 that's going to have to add up to v0 so maybe to get 60 i had you know 50 and 10. and to get 40 for the number fee of one i had 20 and 20. so these these i have to add up um so each level justifies the preceding level that's gonna we're gonna have that happen again um now the prover says well i mean i still don't you know i need to be convinced you know i don't trust you i need to be convinced that these values are correct um so uh level by level the prover is going to be setting more and more of the variables in all the possible ways until it gets down to the very bottom where it's setting the variables to in all possible ways so exponentially many settings here um and the verifier now checks that the previous round was correct so that's where we set only the first m minus one the very last variable hadn't yet been set um so it checks all of those two to the m minus one possible settings um in terms of the new settings that it got where we set those m minus one settings but we extended it by zero and by one and this is that same identity that we used from before um and now now that the proofer has sent all of those possible values rever the verifier needs to be sure that those are still correct but the the thing is is that at this point to verify those are all zeros and ones because they all say whether that assignment satisfies the formula or doesn't satisfy the formula so the verifier can check those directly checks each of those whether just by plugging into the formula and seeing did does it satisfy the formula or not so each one of these is a zero one value which corresponds supposed to correspond to whether the formula was satisfied or not those all are correct um uh and everything else along the way has been correct the verifier is going to accept otherwise if at any point the ver one of those checks failed the verifier is already rejected or at this point it just rejects okay so that is the um the protocol the exponential protocol um and i'd like i i you know not sure if this is helpful to you or not but i like to think of it sort of as a tree of possibilities um so uh these yellow values are what the prover is sending so the approver first sends the number of satisfying assignments all together the verifier in white is checking uh is that are they doing these checks so it checks that it equals k and then the prover sends the next level the verifier checks that the edition works out then the approver sends unpacks it further assigns values to the first two variables and the verifier checks that just the assignments to just a single variable are consistent with that and so on and uh total set assigned all m variables and then it checks directly with the formula now what happens and here is the case it's going to be important to understand both in both here and in the non-boolean case what happens if we had an incorrect value for the input and what i want to show you is that the prover is going to you know i want to show you that the verifier is going to end up rejecting in this case um with certainty later on it's just going to reject with high probability but for this protocol it's going to accept with certainty um and why is that because uh first of all if if the prover if if k was wrong so i'm indicating the wrong value is in red if if if k was wrong so it did not equal the number of satisfying assignments if the approver sends the correct value the premier is just going to be going to say it doesn't match up i reject right away so what is what can the proverb possibly do to prevent the verifier from accepting you're going to see that there's nothing it can do but later on there's a chance that the proverb can get lucky but here there's nothing you can do let's say let's let's try to humor me and see that what let's approve prover try to manage to uh keep the verifier going as long as possible so the approver in order to prevent the verifier from ejecting at the beginning would have to lie about the number of satisfying assignments but then the approver is going to say well okay you know uh you know if you you know you're claiming there's only 99 satisfying assignments proverb doesn't know what the right real answer is but the you know the we know it was a hundred let's say but let's say you know we k was equal to 99 the approver claimed it's 99 now um and so the uh the verifier says okay well it's 99 convince me of that so now the approver is going to have to say the number satisfying assignments for zero and the number of satisfying assignments for one they have to add up at least one of those has to be wrong because you can't have the two correct values adding up to the to the lot to the to to the false value so a lie here has to yield a lie in at least one of those two places and then a lie there is going to have to yield a lie in one of those two places just like you know each lie kind of forces more lies you know as you know you're trying to lie the story gets more and more complicated in order to try to justify all this um and so in the end you're going to get an inequality and the verifier is going to end up rejecting somewhere along the line there's going to have to be an inequality if not along the way then at the very end when the verifier does the check itself because one of those if you trace that down there's going to be lies and lies and lies and then there's going to be a at the very bottom one of these values is going to be wrong and when the verifier checks them all it's going to find out that there is an inequality there and so one of those checks is going to fail okay so um uh so i'm getting one question here why is this any better than just checking all possible assignments without approval you know i yeah it isn't the only reason i'm doing this is to get us ready for the um arithmetized product protocol where we have non-boolean values coming in okay so with questions on this i think it's important to um understand this one don't understand don't ask the question why the why is just going to be we are getting ourselves ready for something later which you don't haven't you don't know yet but i just unders i want you to understand it for what it is even if it seems unnecessarily complicated okay so let's keep going so how we're going to fix that protocol so it's not exponential so again here is a picture of that exponential protocol and you know we have that exponential blow up occurring because at every stage each value is going to be justified in terms of two values at the next stage so it's going to be an exponential exponentially many values after a while so instead we're going to try to justify each value here in terms of just a single value at the next stage but you know it's not going to be good enough just to pick either the zero or the one at random um because it might be each there might be just a single course of lies um going through here and the only way to k would you you would be to catch that would be to guess correctly at each stage which was which was the lie and then you would catch it at the end um if you're just going to be randomly picking zeros and ones um you're not going to have a high probability of catching the prover when it's uh when it's lying and so um that's not going to be good enough you you want you know the the input might be the wrong value and you might have approver which is just has one path of lies um and then your probability you would still have a high probability of accepting in that case even though the input was wrong that's not what you want for the when you have the the input is wrong you have to have only a tiny chance a very small chance of accepting um so the way we're going to achieve that is by having these instead of picking a zero or one for the values of uh for these random values we're going to have non-boolean assignments to the variables and we have to make sense of that and we've already seen an example of that it's going to be very much the same um all right we are we on all we are are we all together here so this is a a place where we could try um uh if you have a question we can try to um answer that um are we good let's keep moving okay so how we going to arithmetize boolean formulas it's again the same idea we had before simulating hands and orders with plus and times so we had this from before same exact picture actually it's even simpler because now we're going to be using the true simulation of or instead of some kind of a special case simulation of war in terms of which we had in the branching program case so these faithfully do what and and or does when you plug in zero for false and one for true so that means that we can take an entire formula and arithmetize it the formula built out of ands and ors and negations and you're going to get a polynomial that comes out um and that polynomial what's going to be important for us is not going to be of extremely high degree the actual degree is going to be at most the length of the formula in terms of the number of symbols it has you can check that on your own you can but for now you can just trust me the degree of the polynomial because it only goes up during the um goes up during the multiplications but the the degree doesn't become too big um uh okay so and we're going to be doing and i don't want this to be a confusing issue here we're going to be doing but you know we have to be correct um i don't want to be cheating here so all of the arithmetic is going to be done in a field so um we have to uh do plus and times mod some uh number which is gonna turns out needs to be a prime number for reasons i'm not gonna get into um but it doesn't really matter it's just modular arithmetic and that's one thing that enables us to pick random values in a natural way because there's only finitely very many values in the field and so you're just going to pick one at random but here we want to be able to represent we it's it's going to be more important for us to have a larger field because we want to be able to represent in the number of satisfying assignments which can be a number between 0 and 2 to the m so we have to have a field which has at least 2 to the m elements in it so that we we can in a sensible way write down those numbers um let's not get caught up with that but um we can try to answer those questions offline if you want um but just think about it for this first pass we're doing the arithmetic mod sum prime okay so now we have the same notion as of presets as we had before so if we have a formula and we preset some of the values but now those values may be non-boolean values we may be setting plugging in values for the formula not just zeros and ones but we might be plugging in sevens or 20 23s or whatever and you know the formula is gonna you know in order to have a value a meaning to that we're gonna treat that formula as the polynomial from the arithmetization and just plug in those values into the polynomial and see what the polynomial does for you so here we're going to be presetting some of the values of the formula like we did before and he now we're going to it's going to be the same thing but now in the polynomial we're going to be pre-assigning some of the values of the variables to these a's which from the field and the remaining variables are going to stay as unset um now we have to give an interpretation now he is um so the new polynomial here okay so i'm getting a question well maybe i better take this let me just let me hold off on that for now uh what the uh degree is um um okay i'll come i'll answer the questions in a second so so now remember from before number fee was the number of satisfying assignments when i preset the first i values it no longer makes sense to talk about satisfying assignments because these values may no longer be booleans so i'm going to have to write this formally um as i'm going to plug in those values those i values for the first i variables and the remaining variables which i have not set i'm going to assign them to zeros and ones in all possible ways only to zeros and ones because what i want to have you know you might think well why you know why not we why aren't we assigning these to other values in the field well because what i'm aiming at is that if i were to plug in zeros and ones at this point into the polynomial i'm supposed to get exactly the same values as i had before because i'm simulating ands and ors so i'm just extending the um the definition the the the the evaluation into a new realm but i shouldn't change the values on the old boolean realm so i'm going to be adding up the unassigned the unset variables in all possible boolean ways and the first i values could be non-boolean values okay so you have to just to accept this as an abstract notion um no longer has an interpretation as satisfying assignments okay so as i said what's important is that for if i if i happen to put boolean values in now then uh fee and number fee get give the same values as they would have before because the polynomial acts identically to the formula on boolean values okay so this is what i'm repeating what i said and there's another point that isn't that's also you know you have to check which is that the identities that we had earlier that connected up what happens when i set the first i values and and i set the first i plus 1 values those still hold so if i set the first i values now to possibly non-boolean some non-boolean assignment that's what i get when i extend those values um to one more a variable being assigned but i just need to assign that variable to zero and to one and add those up because of the way i've defined things over here so i've uh assigned those variables you know i i to zeros the unset variables to zeros and ones you know when i'm defining the um the number fee uh function okay so and then lastly when i assign everything now to possibly non-boolean val values that's going to be there's no longer anything to add up so i'm going to get exactly the same as i got from before when i so assigning number fee of totally preset input it's the same as fee with a totally preset input okay because in that case there are no variables left to add up over so uh there's just one just i just get one single uh my sum has just one element in it okay um so uh i'm getting i got a question here for earlier what happened to the degrees of the polynomials uh well the degree of number fee is going to be at most the degree of fee because i'm just adding things up and addition doesn't change degrees um as i preset values the number of variables goes down but the degree may not necessarily go down so the question was i got is the new are the new polynomials having lower degrees not necessarily they have fewer variables but not a smaller degree okay so let's do this check it let's see if that now again this is i think i have messed up on this so uh well there's one of these that's does it i i i i'll give it away in part there's only one of them that was true anyway so you can check the one that's true according to the way we've we've defined it okay so this is a little bit of a trick question here um as i'll explain but there's only one of them that's faithfully does the arithmetization as i've described on this page and that's the one you should check okay so um remember here over here this is the formula this is the recipe for how i'm doing the arithmetization of this this whole process here so one of these lines one of these a b or c corresponds to doing that okay i'm going to close this down so are we all in yeah so a is the correct answer um a does the arithmetization according to the recipe that i just described because if you look at x1 or x2 you can just look check it in the very first um part of the uh the polynomial x1 or x2 well it's x1 plus x2 minus the product x1 x2 so you can just see it right there the others don't have that um and the similarly for x1 bar and x2 bar it becomes 1 minus x1 1 minus x2 and then the product of those so a is pretty straightforward as the arithmetization of phi now in fact any of those would would work i don't want to confuse you here but any of those would have worked because they all agree on the boolean assignment and that's all that really matters um so if you have any all i care about is that they agree the formula agrees with the polynomial in the boolean cases and these all happen to agree on zeros and ones not doesn't matter though uh i put those there just in case you you tried it by just substitution of zeros and ones in you might you might have picked the wrong thing um okay so let's uh let's take a break here and then we will um see about how to go about fixing the protocol um after the break uh all right so now also happy to take any questions we haven't really done a whole lot we basically this has all been review um of what we did last time um but um let me start the uh timer um and then uh but feel free to ask questions it's the setup is i'll tell you where we're going this whole proof really comes down to understanding one line which is going to be in the second half um so i'm really kind of this is all big set up here to get you ready to be able to understand that one i'll tell you when it's coming so you know you won't you won't have to uh worry that you'll miss it but it's a that line is is not easy to understand so i think it's important to get all of the framework and all of the um uh the context all set up for you so then you can understand that line and and hopefully you know you see that line and understand it okay so uh the important fact um okay so let's go back you wanted to see the important fact um uh [Music] okay um so this is what i was saying before the if i plug in boolean values into the arithmetization i get the same exact thing as i would have if i applied the boolean operations before i did the arithmetization so plus and times in the arithmetization give a faithful simulation of and and or according to these uh little formulas that's that's all i'm saying with this and so if i plug in boolean values for the a's um [Music] i get exactly the same as i would have gotten before i did the arithmetization because the arithmetization is a faithful simulation i'm should i also say it let's see um what does the or rule now why does the or rule now contain the minus a b term while the previous instance of arithmetization didn't because why remember in the case of branching programs we didn't need the minus a b term um over here and that was because we could argue that it was a disjoint or um in the case of the branching programs i don't want to get confusing by trying to explain why that was but in that earlier case we never had took an or of two ones it was an or of zero zero possibly zero one or possibly one zero and so therefore we never had to deal with the case when we had an or of a one one and here we can have that so we have to subtract off that a b term because otherwise we'd have if we just had a plus b then when the one one case we would end up with a two and that would not be a faithful stimulation of the or operation because one or one should be just one not two so a good this is a good question here do all the numbers need to be zeros and ones i'm not sure how negation would work would work with larger numbers so this is um the negation is just you just blindly follow it even though we're going to be plugging in non-boolean values um [Music] you know it's gonna be one minus a seven so you're gonna get minus six you have to do that mod p so whatever mod q so whatever whatever that value you get but um you can no longer think about it as negation in the in the in the former sense now it just becomes a formal thing um you're you're just plugging along doing what the polynomial says numbers are coming out you think you know this is just nonsense but the thing is it's going to have a meaning that's going to be useful to us that's that's what this protocol is going to show yeah so um you can't think about it as negation anymore it's just the negation becomes one minus x in the power in the arithmetized world and you just have to live with that let's see um okay uh another question here if all the fee are equivalent for boolean inputs in the in the check-in um so this is back into this check-in here so if all of the uh p yeah you know so the question is why if they're all equivalent in the boolean case uh why is only a correct um because this is i define piece of fee in a particular way and so this was the value you got if you follow the way i define piece of piece of fee the others would work they just weren't the way i defined it um okay uh any other questions here we should probably move on okay can arithmetization be used in other contexts um uh i often i don't know i there are these two cases where arithmetization works whether there are other cases too i'm actually not sure okay so let's move on so uh our our but our timer is up the candle is burned down okay so this was um okay here we go this is the real protocol um so i'm going to present it to you the way i did before let's think about it with the case first where the input is in the language and we have an honest brewer um so we start off the same way the approver sends fee it sends number fee which in the old sense was the number of satisfying assignments it actually still is because you know since we're not presetting anything there's no non-booleans um in the picture yet so this is going to be the same value as before the verifier checks that k equals number phase so you have to that's why we have to have the big enough field there so that we can um represent numbers up to the number of potential numbers satisfying assignments but that's a side note so but anyway p sends this is exactly what we did before no change the number of satisfying assignments feel like now let's just see let's remember and this is this is one of those cases where not having a big blackboard is hampers us so i'm just going to remind you what we did last time but i'm going to change this so remember before p said sent an unpacked at one level sent the number of satisfying assignments said number uh fee of zero a number fee of one and then v did that check to justify the previous value which the verifier doesn't necessarily trust okay fasten your seat belts everybody this is the whole proof in the next line okay so but it's a doozy um all right is going to send phi of z as a polynomial in z it's going to send just a single object but that object is an entire polynomial and the way it's going to send that is by sending the coefficients of that polynomial okay so let's uh let's um that statement um so first of all um let's understand the value of doing that so if i can send the entire polynomial fee sub z represent that as a polynomial i can plug in 0 and 1 into that polynomial and allow me allow the verifier to do the check that it needs to do to con to um demonstrate that uh number fee is correct so it's going to check that number fee is a number fee of zero plus number fee of one but instead of getting those values directly from the prover it's going to get take that polynomial it got and evaluate that polynomial at zero and one okay so let and just to remember let's go back and remember how we defined uh defined uh number fee to make sure that we understand what it means to have a polynomial here so remember here we're just taking the very first value you could put you are okay with putting a constant 0 or 1 and then adding up over all possible ex extensions all possible boolean extensions to that um and maybe it's okay to put in a non-boolean value here like seven and now you take the remaining variables and it and assign them zeros and ones and all possibilities and add it up now i'm going to do something even a little wilder i'm going to put in a variable for a1 some you know symbolic if you want symbolic value so i'm going to put in a value z for a1 so now i plug in z for a1 here and a2 through am are going to be zeros and ones in all possible ways so i just get a polynomial in z the other variables have been get assigned and added up over the various boolean assignments and now i get some polynomial so i get some expression in z that's just going to be a single variable polynomial okay you whose degree is it going to be at most the degree of number fee so it's degree is not going to be too big um so it sends the coefficient so the degree of that is not too big so there are not too many coefficients to send um so the coefficients are in terms of the xi's no i'm not sure what the mean the coefficients are not in terms the x i's are gone at this point the x i's we've added up the x i's being assigned to zeros and ones in all possible ways so there are no other variables left there's only z um so i'm gonna do the same protocol in a more pictorial way in a minute um so you're gonna see this whole thing twice uh but try to get it you'll have two chances to get this try to get it you know try hard each time um so it's got sensi as a polynomial in z now that's going to be enough for me to figure out which number fee of zero and number fee is of one is because i plug it in for zero and one for for z but now i can figure out what number fee of two is also because i can plug two in for z or number fee of seven i plug seven in for z okay so let's stop here and let's see on other other questions so the so is the size of number fee i don't understand the so this question about the size of number fee um is it is it 2 to the n no it's not 2 to the m because the degree of that polynomial uh number phi of z i mean you know it's a very large expression if you want to initially you know yes writing that it's going to be an exponentially big sum but the prover adds it all up for you and you're just going to have at most a small number of coefficients because the polynomial is only of a certain degree and a polynomial in one variable of degree d has the most d or d plus one coefficients to worry about so it's not that many coefficients as an expression so um shouldn't the summation take 2 to the m time i'm not caring about the prover's time the prover has a lot of work to do but the prover prov sends fee of z so uh the prover yes the proofer has a an exponential job i don't care the verifier always needs to be able to check it in polynomial time and that checking is gonna well we'll have to see how does the verifier know that that polynomial was right that's a question you may maybe you should be asking um yeah okay i'm getting lots of questions about how much time the prover needs to take yeah the proof is going to have to spend exponential time to figure out that polynomial but that's all right we're not we don't care about the provers time um yeah so the summation here is going to be adding up polynomials that is correct i'm happy to spend time because really here this is the whole proof you have to understand well we have to understand why this works but um we kind of understand half of it because knowing that polynomial is enough to you know if you could certify that that was the correct polynomial for a number fee of z then we can use that polynomial to to confirm the previous value what number fee was because you just plug in zeros and ones for this for z and you add it up but now how are we going to justify that the polynomial is correct because this looks like even a worse job now we have a whole bunch of coefficients and have to make sure all of those coefficients are right and so instead of just two values now we have like d values where d is the degree of that polynomial which could be at most like the length of the formula um uh so here is the next idea um so the prover needs to show that phi of z is correct okay um the way it's going to do that let's say so even before before we do that so fee of z is going to be some polynomial um now the prover may be lying maybe sending the wrong polynomial how does the prover convince the verifier that the power that that polynomial is the right polynomial well that seems like a tough job so what it's going to do is remember that the um there is so there you know there is there is a correct polynomial that you would get by plugging into this expression for the for the correct value so there's some correct polynomial the prover may be sending some some incorrect polynomial but now those so now we have the correct polynomial and the possibly incorrect polynomial which and the point is those two can only agree in a small number of places by that fact that we proved a couple of lectures back regarding polynomials so two different polynomials can agree only rarely so what we're going to do the way the prover is going to justify that this polynomial was the correct one is by evaluating it at a random place and then demonstrating that that value you get is a correct value if the polynomial was the wrong polynomial then evaluating it at a random place is probably going to disagree with the correct polynomial at that place because they can only agree rarely so the prover is going to demonstrate that by evaluating that polynomial at a random place that value you get is going to be the correct value and it's going to continue to do that in the way using the same protocol as we'll see so that's where we're going so to in order to show that figure z is correct the verifier now gets to pick a random value in the field and the prover is going to show that evaluating that polynomial at r1 is correct remember this looks a lot like what we had from before where we were val showing that number fee of zero is correct the number fee of one is correct now we're trying to show that number fee of r1 this random value from the field is correct so the way we're going to do that is now by unpacking it one level down we're going to be using those identity that identity by because this value here is going to be equal to um number fee of r1 comma 0 plus number fee of r1 comma 1. so the way but we don't want to send both of those so we're going to send them combined into a polynomial of number fee of r1 of z as a polynomial in z this is the new polynomial in z okay so now if you understood the previous line then hopefully this one won't be too hard to swallow because now we're going to check um the identity but here by evaluating the polynomial again but one level at the next level okay so this is this is um uh perhaps a good place to uh to take questions because this is this is the heart this is really what i spent all the time setting things up for so that you would be ready to get this thing hopefully without you know and hopefully get be able to appreciate it and understand okay so um so let's let i'm not getting questions let's let's move on a little further so now in order so the pollen again the approver has sent this polynomial at the next in stage two um now we the verifier needs to be sure that that polynomial is correct so it's going to evaluate um that polynomial that new polynomial um at a random location um so by picking a random value r2 in in um in the field uh and now it needs to show that this value is is correct um because if that polynomial had been the wrong polynomial it disagreed with the correct polynomial almost everywhere and by picking a random place it's probably not going to be the right value and we'd s all of the values have been picked and so we have one last value um uh to to select a zero and one this corresponds to the nth you know if you it would be great if i could put both pictures on um on your screen but i can't um so this very much corresponds to what happened in the exponential protocol but just along you know sort of this arithmetic arithmetized one single path so uh it checks that the previous value is is correct in terms of expanding it with zero and one but again the zero and one comes from evaluating the polynomial um and now the verifier needs to be convinced that that polynomial was right so it picks a random value but now it doesn't rely on the prover anymore it's going to see whether that that assignment that it gets by evaluating the polynomial with that random value rm plugged in is the same as what i get by evaluating the polynomial for the formula itself that the verifier can do directly because this is now a polynomial now just plugging into the formula and using the arithmetization to get a value out okay so this was the last line of the identity okay we had those two identity those two identities so this is the second identity and we have to check that this is correct okay so uh so i'm gonna describe show this to you in a picture uh not sure it'll help if you're if you're confused but why don't we take some questions on this so as i said i'm going to give you two chances to understand this um because i know it's tough this is especially with the constraints of zoom this is a particularly challenging idea to explain okay so let's see so the benefit of this approach is that the approver only sends one item for each depth level instead of multiple items that's right but that one item is the polynomial so that that captures all of the values for the entire field but taking advantage of the arithmetization that one polynomial you know us has a lot of information in it and what's nice is that you can check that polynomial by just evaluating it at random one random place you can check that that polynomial is correct um okay um so where does so i'm getting another question here where does this come from here if we we checks that this here so this where does this so you have to look to understand why where this is coming from you have to we're at the end round now so you have to look back like at round two v has to check that fee of r1 which comes from the end of the first round so this checks that this fee of r1 is correct because that was where that was how we justified the polynomial with just a single variable the the very first polynomial is correct you know a little hard to say but this comes from the previous round this this guy here um okay so this is the polynomial for the current round this is the value from the previous round all right more questions so so why doesn't this run for exponential time another question i'm getting doesn't v need to check twice at each layer yes if the the verifier needs to check um gets two values but those two values come from the one polynomial so there's no blow up anymore you know those two values maybe you'll see it in the picture that i'm going to show so maybe just hold that question and maybe this will become clearer in the in the diagram so another question does this work because the polynomial encodes kind of encodes all the possible values together i think that's sort of true that sort of mixes them all together into one object then you have to check that one object which can be done with a sort of random probing of it um okay so so this is another good question that we'll see explained in the next slide so uh so similarly in attempt one the prover can keep lying by by picking polynomials um in rounds one you know by continuing to pick polynomials by lying about the polynomials but eventually it's going to get caught because this value is going to be the wrong value you know if the polynomial in the previous stage and the m minus f you know if it's a polynomial that the prover sent in the m state is the wrong polynomial then you evaluate it you're going to get the wrong value probably um and so then that wrong value is not going to match the correct value which is you can read you off yourself by reading the formula okay i think we should need to move on to the next slide um all right so same proof version two but looks different um again the input is that here's what the approver sends here is what the verifier sends i'm gonna i sort of whimsically designed this as a uh as a telephone chat where they're sending each method messages through uh messaging okay so the prover sends uh the number fee to start off with and then off on the side these are the checks that the verifier is going to be doing so here in our first round of the chat the approver is going to send fee of z remember this is just a a polynomial in not too many coefficients so it's a polynomial in one variable the degree is small so there are not too many coefficients here you know so this is uh so pretending this is what it might look like and then the verify so from that polynomial the verifier can plug in zero and one and see that the adds up um now the verifier to check that this polynomial is correct it picks a random value to evaluate this polynomial on um uh and so now it's going to have to check that this is correct so this is not nothing to check you're just writing this down in anticipation of the next check now the prover to justify that that this value is right that that this polynomial is right so we evaluate okay doesn't say that to prove in order to check that this value is right is going to send the polynomial for the next level um now we can from that we can plug in zero and one for z see if that adds up and now to be sure that this polynomial is right um we evaluate it at a random place calculate that value and then um uh have to have to see that this value is correct so now we expanded one level down further we pick a we we take a polynomial for the next variable and we see that it adds up okay i i'm not i'm not sure what whether this is helping or not um but we keep doing that until we get to the very last round uh where the prover's sending a polynomial make sure that this adds up correctly um and the verifier to be see that this polynomial is right picks a random value and uh evaluates it and now checks that this agrees with the formula because we've now assigned all of the variables and the then we can then we can check this number fee directly in terms of the fee um because they have to agree okay and so the verify would accept if everything checks out let's see what happens so this answer will answer some questions um why don't i go walk through what happens if um the input was wrong and we'll we'll see how the verifier is likely to catch the approver but not guaranteed to catch the approver in this case um so if k was correct the verifier will accept with the honest prover but if k was wrong so i'm going to again indicate the wrong values in red um i'm going to show you that the verifiers is almost certainly going to accept but not guaranteed so uh did i say that wrong so if k is wrong the verifier is going to probably reject but it's not guaranteed to reject so um first of all if the does not lie does not send the wrong value for a number fee the verifier is certainly going to reject because it's not going to be get any quality there um so the prover has to lie you know say you know um you know if k was 99 but the real value was 100 the approver if it says 100 the verifier is going to reject immediately so the verifies you know the proof is going to say well let's let's see what what the approver can do to make the verifier uh hopefully accept from the approver's standpoint so the proof is going to send 99. well the verifier says okay 99 fine uh convince me so the program now um you know one of these two has is going to be wrong uh has to be because the two correct values can't add up to the wrong value so one of these is wrong so that means the prover had to send the wrong polynomial because the correct polynomial would evaluate the correct answers here so the prover had to send the wrong polynomial so now when we evaluate it at a random place chances are this is going to be the wrong this is not going to be the same value that the correct polynomial would have given you the prover could get lucky we could have verified it might have just happened to pick a place with a correct polynomial and the incorrect polynomial agree and that place the approval think huh i'm saved now i can act like the honest prover from this point on and you know the verifier will never catch me you know i said a little bit analogous to the situation maybe you know you know i'm trying to see if you really studied the whole course so i'm giving you an exam but by picking sort of random places there but maybe you just studied you know a few facts from the from the course you might get lucky i might happen to ask just about those facts and then you give the appearance of having studied everything but you really didn't so here the approver might send the wrong polynomial but the verifier just queries that at the place where it happens to agree with the correct polynomial and the verb just gets lucky and the verifier is going to accept in that case but there are very few of those so that's why the prover is almost certainly to be caught if it tries to lie but not guaranteed um so again so just tracing this down uh if this was a lie then one of those two has to be a lie so therefore the next polynomial has to be a lie and so we continue so then the next value is almost certainly going to be a lie not guaranteed and so then one of those two values has to be a lot at least one has to be a lie therefore the polynomial has to be a lie and so on um uh until uh you know unless the approver got lucky along the way somewhere which is very unlikely even though it has several opportunities you know we've arranged ranges so that the chance of getting lucky is tiny at each stage so even though he has a few chances there's still going to be a tiny chance that you're going to get lucky somewhere and so this is wrong then chances are that's wrong and so therefore this is going to be a disagreement and the verifier at that point when it doesn't agree it's going to reject unless the people got lucky somewhere along the way which is unlikely okay so uh i don't know if you had so that's my all i was going to say about this proof uh i don't know if you had any questions on it but let's just see okay so [Music] uh do we have any questions i can answer how the approver gets how how does approver get number how does the prover get number fee of z um so you have to you know why is number fee of z have no other variables you have to go back and look at the the definition of number fee of number fee of a because you add up over all the other variables so now we're pick plugging in instead of a plugging a variable for that but you're still adding up over the other variables so this is a very column this is a function in just one variable which is about who can because it's you know it was original original thing was a polynomial so so this is also going to be following um i think we're starting to run low on time so this is our very last check-in for the semester here so of course there's one natural question to ask you all and for our very last check-in as we're in our last couple of minutes of the course or the least of the lectures does p equal np what do you think will maybe pb equal np be solved by a deep learning algorithm or maybe we'll never prove it give me your best guess okay we're kind of running out of time so let's not think too hard here um another five seconds all right ending polling uh i'll share that with you oh yeah i did share uh so what what do we get d here we will prove it in somewhere between 20 and 100 years from now that's the seems to be the majority opinion uh i don't know i hope it'll be sooner than that because i'd like to see the answer but uh we don't know uh uh yeah if you can prove peter from np yeah yeah i'll give you an a plus you won't have to take the final but you better be sure you're right um all right so what that is our quick review we finished number sat in ip and therefore that co-np is a subset of ip um if you're interested in further pursuit of this material i got a couple of questions on that these are some courses you may want to look at um i know i checked with um ryan williams he's planning to teach advanced complexity uh fall 2021 so um uh that's we're going to be one the most natural follow-on subject to this one is the crypto classes also are kind of make use of some of the same ideas and there's of course also randomness computation that ronit rubenfeld teaches i don't know if i didn't check with her i don't sure the next time she's going to be teaching that um and uh good luck on the final and best wishes so um and i'm gonna have office hours so if you have any questions uh you know happy to uh answer those but otherwise see you all good luck thank you for the comments yeah i enjoyed having you all as students it was it was uh it was a fun time a lot of work but it was a fun time i've always been intrigued by p the p versus np problem and i proved a kind of a i proved the exponential complexity of computing the parity function in a certain weak model of computation so parity function is very obviously very trivial function um but the for the parity function if you can't count whatever that means but there's a there is a model you can kind of set up but you can't count then parity requires exponential complexity and surprisingly not easy to prove uh but that's probably the theorem that i'm most known for anyway but that would be a topic for another day um another question why not include my hills the my hill and the road theorem seems i don't know that's a theorem about finite automata and all of those ways of characterizing the regular languages that seems kind of a tactic technical theorem i don't don't see much point in covering it and another question that some of my colleagues ask me is why don't i have rice's theorem which is sort of provides a kind of a machine for proving undecidability and uh i don't know i think that you can use rice's theorem without understanding how to prove undecidability it becomes sort of uh it's like a it's like checking off checking off a box checking some boxes and then you get conclude something's undecidable i'd rather have somebody understand it rather than just be able to use some powerful tool um can we understand that proof of the num the proof about the parity function uh that i just alluded to that's super hard you can with the knowledge from this class i think you can um the the that theorem uh relies on a certain technique which we didn't cover uh called the probabilistic method which is a kind of an amazing method uh not hard to explain but basically you show that something exists by showing that the probability that a random object has the property you're looking for is more than zero um and so therefore the thing that you're looking for that has that property has to exist um there are lots of examples of that these days but it's it's kind of an amazing method so use that method do i think quantum computing can solve useful problems beyond the capability of classical computers i have no idea whether one can really build a quantum computer it seems to be always 20 years off at least to doing one that factors and i've been literally uh i remember people 20 years ago saying it's 20 years off so uh i don't think it's converging um i i'm skeptical that they'll ever build a chronic computer that can factor i'll go out on a limb and say that but that's controversial um and whether it can solve other useful problems i'm not sure whether useful problems are there well i guess they're simulating quantum systems so maybe that that might be possible um all right i think i'm gonna i'm gonna end this now but thank you everybody take care bye you 3 00:00:27,039 --> 00:00:28,070 greetings everybody uh welcome to our last lecture of the term we have survived a a semester online in 18404 and um we are going to conclude our last topic today which is interactive proof systems that we started last time and um with the big well the um uh the big theorem of interactive proof systems is that um i p equals p space and we're going to give the main idea for that in a slightly weaker uh theorem um as we'll see so uh why don't we jump in um so today's uh we have been doing interactive proofs we gave an example of showing that the graph isomorphism problem the complement of that is an ip as you i hope you remember we had those that interaction with approver and verifier we're going to go through it quickly not that protocol but just this setup and then we're gonna uh finish uh by showing that this numbersat problem is an ip and conclude that cohen p is a subset of ip all right so let's go for it um [Music] yes um so just remember interactive proof systems there were these two parties the approver and the verifier the approver has unlimited computational ability um i kind of uh you know uh modeled that as a an army of students perhaps who are uh have who can um where we where we don't uh they can work all night they can use computational resources and um the prover however we're not gonna measure the computational power of the approver that's unlimited and so the approver can do things like find certificates it can test whether things are satisfiable it can factor numbers we don't care they can do whatever we'd like and there's no charge for the provers computational um demands okay so the setup we had was the approver and the verifier both see the input they exchange a polynomial number of messages and then the verifier accepts or rejects and we had this notion of the probability that the verifier ends up accepting when paired with a particular prover and we what we want is that for strings in a language that probability should be high for some prover and for strings not in the language that prover that probability should be low no matter what the prover does so there's nothing the prover can do um and the way it kind of suggests that any particular any prover but whatever the provers strategy um cannot make the verifier accept with high probability just doesn't have enough information or it doesn't it's just not able to make the verifier accept with high probability um i i uh you know you might think of the prover is trying to make the verifier accept so you know that pete tilda is a crooked prover i didn't i don't think that that was went down very well with everybody so i i have it here another way of looking at it maybe it looks a little bit more like np here where um ip is the collection of languages where there's a verifier just like we had you can think of np as a having a verifier which can check certificates here the prover is going to be like the certificate so that for strings in the language there's approver which can interact with the verifier and make it accept with high probability and you're not in the language there is no prover which can interact with the verifier and make the verifier accept with even more than low probability what's important is this gap just like with bpp between acceptance or rejection and that gap is there because we want to be able to use the amplification lemma and if there was no gap then you wouldn't be able to amplify and make a make the probability of acceptance extremely high when you want it to be in the language when you're in the language and extremely low when you're not in the language um okay so i hope that gives you you know refreshes your memory as to how that works we're gonna um walk ourselves through the um uh um [Music] well through that what we did last time but let's set the stage for that so the surprising theorem as i mentioned is that i p equals p space um one direction of that is a fairly standard simulation you if with p space you can basically work your way through the tree of possibilities for an interactive proof uh protocol and you can calculate the probability that the verifier would end up accepting if you had the best possible approver that would make try to make the verifier accept and you can just do that calculation it's in the book um you're not going to be responsible for knowing that actually we haven't covered it in lecture but it's not very hard um a little technical i suppose the other direction is the interesting one and that's the direction we're going to be moving toward today we won't quite get there um but the way it works is that uh to show that everything in p space which is kind of amazing um is contained with an ip so everything in p space can be done in i with an interactive proof system and the way that is done is by using a piece based complete problem tqbf and showing that that problem itself is an ip uh but we we we're not going to prove that um that would be sort of the next thing we would prove if we had a little bit more time but um we're going to be satisfied with just the somewhat weaker but very similar statement that cohenp cohen p is contained in ip here again still very surprising because you have to be able to show for example that a formula is not satisfiable with approver how can approver convince a verifier that a formula is not satisfiable um you know the showing that it is satisfiable you just give the certificate which is the satisfying assignment but how do you show something's not satisfiable it's unexpected um and the proof of that is pretty much similar slightly is one kind of technical point which we don't have to get into so it's slightly easier but very much in the same spirit so remember this number set problem is you're given a formula and a number and the that number is supposed to be exactly the number of satisfying assignments of the formula um so in particular formula is unsatisfiable then it would be paired with the number zero and that's why uh the number set problem is cohen p hard because you can easily reduce the unsatisfiable unsatisfiability to number set and unsatisfiability is uh coinp complete okay so remember we introduced this notation last time this is going to be critical for understanding this proof so let's go through it once again so if you have some formula what i like to do is preset some of the variables of that formula so that's going to be a formula on m variables x1 to xm and i'd like to preset the first i variables to certain to zeros or ones as i wish um so i'm going to indicate that by fee with 0 means i'm setting x1 to 0 and the rest of the variables remain variables um and more generally fee of five i values a one to a i which are going to to start off with are going to be just zeros and ones just boolean values that's going to be the formula with those first x1 to set to a1 dot dot x i set to ai for those i constants um which are zeros and ones um i'm going to call those presets because we're presetting some of the values of the some of the variables in the formula and the rest of the variables we're going to leave as variables so we get a new formula on fewer variables by doing this pre-setting process and we're going to get to do the same thing in terms of counting the number of satisfying assignments so remember the notation number fee is the number of satisfying assignments number fee with a preset of zero is the number of satisfying assignments when you've set x1 to zero and number fee of a1 to ai is where you set the first i variables to those i values and then you're going to look at the number of satisfying assignments with those presets in mind okay so there were two facts i'm going to call them identities because we're going to um rely on those and we're going to actually extend those to the non-boolean case as we'll see shortly so um these two identities say that um uh first of all if i preset i i think the understanding the first one is clear just by thinking about it in the case where i equals zero so this is the case where the number of satisfying assignments altogether is the number of satisfying assignments when i've set x1 to 0 plus the number of satisfying assignments when i've set x1 to 1. and this just generalizes that when i look at having already preset the first i variables so if i preset the first i variables to these i values that the number of satisfying assignments i get there is the number of satisfying assignments i get with those presets plus the next variable being set either to zero or to one and then you add those up the same idea and lastly if i set all of the variables to values so i have no variables left and i look at the number of satisfying assignments consistent with that fully set um variables so there's no variables left everything is set everything is preset that's just whether or not those values have satisfied the formula already or not so this is going to be equal to zero or one the number of consistent satisfying assignments with those m presets where m is the number of variables is just whether those m values satisfy the formula which case i get a one or they don't satisfy the formula in which case i get a zero okay critical to understand these in the boolean case because we're going to generalize this to the non-boolean case and it's going to be just more abstract the formulas are going to look the same but we're going to have to um kind of we're going to lose the intuition that those things correspond to satisfying assignments or counting the number of satisfying assignments all right let's have a quick check in here um so let's we're just going to do an example to hope to you know nail this in this idea so here's a particular formula fee um and now remember number fee is the number of satisfying assignments a fee the number of satisfying assignments where i've set x1 to 0 and so on okay so just and here i'm really kind of giving you two options in in each row for the value now you have to check all that are true so it's really going to be one at most one per row presumably um all right let's see how if your file if you're with me here so the number of satisfying assignments uh for uh altogether well there are two ways of satisfying this formula either um this is really like exclusive or um so either x1 is 1 x2 is 0 or x1 is 0 and x2 is 1. so one of the value variables has to be true the other one has to be false and then you're going to end up satisfying both clauses as you can easily see um so b is b is correct in the first line now if i'm going to already commit to saying the first variable is set to zero now how many satisfying assignments can there be well the second variable just has to be set to one in order to satisfy so now there's going to be only one satisfying assignment consistent with setting the first variable to zero now if i set the both variable both variables to zero now how many satisfying assignments can there be consistent with that assignment they can be zero because um if uh in order to satisfy this formula one of the variables has to be zero the other one has to be one if i'm presetting them both to zero there's not going to be any satisfying assignments because zero zero does not satisfy the formula okay apologies for messing up that uh uh checking on the last day oh well um all right let's get let let's first go over the um uh the protocol we attempted for number sat uh last week um on thursday okay so we're given the input the formula and a k and remember what we want to happen we want the verifier to end up accepting with high probability when k is the correct value and with low probability when k is the not c not the correct value um now this is going to be as you may remember from last time this is going to end up being a flawed protocol because it's exponential we're only allowed to be have a polynomial size protocol but um just looking ahead in this protocol the verifier is going to end up accepting with probability one for an honest approver and with probability zero no matter what the prover tries to do so for any prover um the probability the verifier can cannot be made to accept so this is kind of an extreme case um where there's not going to end up being any probabilities but it's an exponential protocol so in that sense it doesn't do what we need so let's go through it because it really sets us up for the polynomial protocol with the non-boolean values all right so first the prover sends um let's just look at it and not rush it the approver sends um the [Music] number of satisfying assignments according to the approver the verifier checks that is equal to k and i think it's best to understand this first with the case that the input is in the language so k is correct and we have an honest prover and then we'll understand what happens if k is not in the language and we'll see that no matter what the prover tries to do the verifier is going to end up not accepting um and again you know this is just a setup for the real protocol so this is kind of a dopey protocol you're going to think what what the world and why am i doing this um it's not uh it seems like i'm making something that's very simple complicated but it's really just the framework that i'm i'm putting together because well you'll see all right so the proof is going to send the claim for the number of satisfying assignments um which in the honest case is going to be the correct value the verifier checks that it matches the input now the verifier says well i want to be convinced that your claim is correct so the approver is going to justify that claim by saying well the total number of satisfying assignments is whatever it is a hundred because the number when i have x1 set to zero um is 60 and the number when i have x1 set to 1 is 40. and that adds up to 100 which is what you would need to have happen so the verifier checks that the sum is correct and then says well now how do i know those two values are right so then the approver unpacks it one level further so breaks those two down by uh justifying that fee 0 was correct that value 60 was correct by saying well now if i set the next variable x2 to 0 and 1 that's going to have to add up to v0 so maybe to get 60 i had you know 50 and 10. and to get 40 for the number fee of one i had 20 and 20. so these these i have to add up um so each level justifies the preceding level that's gonna we're gonna have that happen again um now the prover says well i mean i still don't you know i need to be convinced you know i don't trust you i need to be convinced that these values are correct um so uh level by level the prover is going to be setting more and more of the variables in all the possible ways until it gets down to the very bottom where it's setting the variables to in all possible ways so exponentially many settings here um and the verifier now checks that the previous round was correct so that's where we set only the first m minus one the very last variable hadn't yet been set um so it checks all of those two to the m minus one possible settings um in terms of the new settings that it got where we set those m minus one settings but we extended it by zero and by one and this is that same identity that we used from before um and now now that the proofer has sent all of those possible values rever the verifier needs to be sure that those are still correct but the the thing is is that at this point to verify those are all zeros and ones because they all say whether that assignment satisfies the formula or doesn't satisfy the formula so the verifier can check those directly checks each of those whether just by plugging into the formula and seeing did does it satisfy the formula or not so each one of these is a zero one value which corresponds supposed to correspond to whether the formula was satisfied or not those all are correct um uh and everything else along the way has been correct the verifier is going to accept otherwise if at any point the ver one of those checks failed the verifier is already rejected or at this point it just rejects okay so that is the um the protocol the exponential protocol um and i'd like i i you know not sure if this is helpful to you or not but i like to think of it sort of as a tree of possibilities um so uh these yellow values are what the prover is sending so the approver first sends the number of satisfying assignments all together the verifier in white is checking uh is that are they doing these checks so it checks that it equals k and then the prover sends the next level the verifier checks that the edition works out then the approver sends unpacks it further assigns values to the first two variables and the verifier checks that just the assignments to just a single variable are consistent with that and so on and uh total set assigned all m variables and then it checks directly with the formula now what happens and here is the case it's going to be important to understand both in both here and in the non-boolean case what happens if we had an incorrect value for the input and what i want to show you is that the prover is going to you know i want to show you that the verifier is going to end up rejecting in this case um with certainty later on it's just going to reject with high probability but for this protocol it's going to accept with certainty um and why is that because uh first of all if if the prover if if k was wrong so i'm indicating the wrong value is in red if if if k was wrong so it did not equal the number of satisfying assignments if the approver sends the correct value the premier is just going to be going to say it doesn't match up i reject right away so what is what can the proverb possibly do to prevent the verifier from accepting you're going to see that there's nothing it can do but later on there's a chance that the proverb can get lucky but here there's nothing you can do let's say let's let's try to humor me and see that what let's approve prover try to manage to uh keep the verifier going as long as possible so the approver in order to prevent the verifier from ejecting at the beginning would have to lie about the number of satisfying assignments but then the approver is going to say well okay you know uh you know if you you know you're claiming there's only 99 satisfying assignments proverb doesn't know what the right real answer is but the you know the we know it was a hundred let's say but let's say you know we k was equal to 99 the approver claimed it's 99 now um and so the uh the verifier says okay well it's 99 convince me of that so now the approver is going to have to say the number satisfying assignments for zero and the number of satisfying assignments for one they have to add up at least one of those has to be wrong because you can't have the two correct values adding up to the to the lot to the to to the false value so a lie here has to yield a lie in at least one of those two places and then a lie there is going to have to yield a lie in one of those two places just like you know each lie kind of forces more lies you know as you know you're trying to lie the story gets more and more complicated in order to try to justify all this um and so in the end you're going to get an inequality and the verifier is going to end up rejecting somewhere along the line there's going to have to be an inequality if not along the way then at the very end when the verifier does the check itself because one of those if you trace that down there's going to be lies and lies and lies and then there's going to be a at the very bottom one of these values is going to be wrong and when the verifier checks them all it's going to find out that there is an inequality there and so one of those checks is going to fail okay so um uh so i'm getting one question here why is this any better than just checking all possible assignments without approval you know i yeah it isn't the only reason i'm doing this is to get us ready for the um arithmetized product protocol where we have non-boolean values coming in okay so with questions on this i think it's important to um understand this one don't understand don't ask the question why the why is just going to be we are getting ourselves ready for something later which you don't haven't you don't know yet but i just unders i want you to understand it for what it is even if it seems unnecessarily complicated okay so let's keep going so how we're going to fix that protocol so it's not exponential so again here is a picture of that exponential protocol and you know we have that exponential blow up occurring because at every stage each value is going to be justified in terms of two values at the next stage so it's going to be an exponential exponentially many values after a while so instead we're going to try to justify each value here in terms of just a single value at the next stage but you know it's not going to be good enough just to pick either the zero or the one at random um because it might be each there might be just a single course of lies um going through here and the only way to k would you you would be to catch that would be to guess correctly at each stage which was which was the lie and then you would catch it at the end um if you're just going to be randomly picking zeros and ones um you're not going to have a high probability of catching the prover when it's uh when it's lying and so um that's not going to be good enough you you want you know the the input might be the wrong value and you might have approver which is just has one path of lies um and then your probability you would still have a high probability of accepting in that case even though the input was wrong that's not what you want for the when you have the the input is wrong you have to have only a tiny chance a very small chance of accepting um so the way we're going to achieve that is by having these instead of picking a zero or one for the values of uh for these random values we're going to have non-boolean assignments to the variables and we have to make sense of that and we've already seen an example of that it's going to be very much the same um all right we are we on all we are are we all together here so this is a a place where we could try um uh if you have a question we can try to um answer that um are we good let's keep moving okay so how we going to arithmetize boolean formulas it's again the same idea we had before simulating hands and orders with plus and times so we had this from before same exact picture actually it's even simpler because now we're going to be using the true simulation of or instead of some kind of a special case simulation of war in terms of which we had in the branching program case so these faithfully do what and and or does when you plug in zero for false and one for true so that means that we can take an entire formula and arithmetize it the formula built out of ands and ors and negations and you're going to get a polynomial that comes out um and that polynomial what's going to be important for us is not going to be of extremely high degree the actual degree is going to be at most the length of the formula in terms of the number of symbols it has you can check that on your own you can but for now you can just trust me the degree of the polynomial because it only goes up during the um goes up during the multiplications but the the degree doesn't become too big um uh okay so and we're going to be doing and i don't want this to be a confusing issue here we're going to be doing but you know we have to be correct um i don't want to be cheating here so all of the arithmetic is going to be done in a field so um we have to uh do plus and times mod some uh number which is gonna turns out needs to be a prime number for reasons i'm not gonna get into um but it doesn't really matter it's just modular arithmetic and that's one thing that enables us to pick random values in a natural way because there's only finitely very many values in the field and so you're just going to pick one at random but here we want to be able to represent we it's it's going to be more important for us to have a larger field because we want to be able to represent in the number of satisfying assignments which can be a number between 0 and 2 to the m so we have to have a field which has at least 2 to the m elements in it so that we we can in a sensible way write down those numbers um let's not get caught up with that but um we can try to answer those questions offline if you want um but just think about it for this first pass we're doing the arithmetic mod sum prime okay so now we have the same notion as of presets as we had before so if we have a formula and we preset some of the values but now those values may be non-boolean values we may be setting plugging in values for the formula not just zeros and ones but we might be plugging in sevens or 20 23s or whatever and you know the formula is gonna you know in order to have a value a meaning to that we're gonna treat that formula as the polynomial from the arithmetization and just plug in those values into the polynomial and see what the polynomial does for you so here we're going to be presetting some of the values of the formula like we did before and he now we're going to it's going to be the same thing but now in the polynomial we're going to be pre-assigning some of the values of the variables to these a's which from the field and the remaining variables are going to stay as unset um now we have to give an interpretation now he is um so the new polynomial here okay so i'm getting a question well maybe i better take this let me just let me hold off on that for now uh what the uh degree is um um okay i'll come i'll answer the questions in a second so so now remember from before number fee was the number of satisfying assignments when i preset the first i values it no longer makes sense to talk about satisfying assignments because these values may no longer be booleans so i'm going to have to write this formally um as i'm going to plug in those values those i values for the first i variables and the remaining variables which i have not set i'm going to assign them to zeros and ones in all possible ways only to zeros and ones because what i want to have you know you might think well why you know why not we why aren't we assigning these to other values in the field well because what i'm aiming at is that if i were to plug in zeros and ones at this point into the polynomial i'm supposed to get exactly the same values as i had before because i'm simulating ands and ors so i'm just extending the um the definition the the the the evaluation into a new realm but i shouldn't change the values on the old boolean realm so i'm going to be adding up the unassigned the unset variables in all possible boolean ways and the first i values could be non-boolean values okay so you have to just to accept this as an abstract notion um no longer has an interpretation as satisfying assignments okay so as i said what's important is that for if i if i happen to put boolean values in now then uh fee and number fee get give the same values as they would have before because the polynomial acts identically to the formula on boolean values okay so this is what i'm repeating what i said and there's another point that isn't that's also you know you have to check which is that the identities that we had earlier that connected up what happens when i set the first i values and and i set the first i plus 1 values those still hold so if i set the first i values now to possibly non-boolean some non-boolean assignment that's what i get when i extend those values um to one more a variable being assigned but i just need to assign that variable to zero and to one and add those up because of the way i've defined things over here so i've uh assigned those variables you know i i to zeros the unset variables to zeros and ones you know when i'm defining the um the number fee uh function okay so and then lastly when i assign everything now to possibly non-boolean val values that's going to be there's no longer anything to add up so i'm going to get exactly the same as i got from before when i so assigning number fee of totally preset input it's the same as fee with a totally preset input okay because in that case there are no variables left to add up over so uh there's just one just i just get one single uh my sum has just one element in it okay um so uh i'm getting i got a question here for earlier what happened to the degrees of the polynomials uh well the degree of number fee is going to be at most the degree of fee because i'm just adding things up and addition doesn't change degrees um as i preset values the number of variables goes down but the degree may not necessarily go down so the question was i got is the new are the new polynomials having lower degrees not necessarily they have fewer variables but not a smaller degree okay so let's do this check it let's see if that now again this is i think i have messed up on this so uh well there's one of these that's does it i i i i'll give it away in part there's only one of them that was true anyway so you can check the one that's true according to the way we've we've defined it okay so this is a little bit of a trick question here um as i'll explain but there's only one of them that's faithfully does the arithmetization as i've described on this page and that's the one you should check okay so um remember here over here this is the formula this is the recipe for how i'm doing the arithmetization of this this whole process here so one of these lines one of these a b or c corresponds to doing that okay i'm going to close this down so are we all in yeah so a is the correct answer um a does the arithmetization according to the recipe that i just described because if you look at x1 or x2 you can just look check it in the very first um part of the uh the polynomial x1 or x2 well it's x1 plus x2 minus the product x1 x2 so you can just see it right there the others don't have that um and the similarly for x1 bar and x2 bar it becomes 1 minus x1 1 minus x2 and then the product of those so a is pretty straightforward as the arithmetization of phi now in fact any of those would would work i don't want to confuse you here but any of those would have worked because they all agree on the boolean assignment and that's all that really matters um so if you have any all i care about is that they agree the formula agrees with the polynomial in the boolean cases and these all happen to agree on zeros and ones not doesn't matter though uh i put those there just in case you you tried it by just substitution of zeros and ones in you might you might have picked the wrong thing um okay so let's uh let's take a break here and then we will um see about how to go about fixing the protocol um after the break uh all right so now also happy to take any questions we haven't really done a whole lot we basically this has all been review um of what we did last time um but um let me start the uh timer um and then uh but feel free to ask questions it's the setup is i'll tell you where we're going this whole proof really comes down to understanding one line which is going to be in the second half um so i'm really kind of this is all big set up here to get you ready to be able to understand that one i'll tell you when it's coming so you know you won't you won't have to uh worry that you'll miss it but it's a that line is is not easy to understand so i think it's important to get all of the framework and all of the um uh the context all set up for you so then you can understand that line and and hopefully you know you see that line and understand it okay so uh the important fact um okay so let's go back you wanted to see the important fact um uh [Music] okay um so this is what i was saying before the if i plug in boolean values into the arithmetization i get the same exact thing as i would have if i applied the boolean operations before i did the arithmetization so plus and times in the arithmetization give a faithful simulation of and and or according to these uh little formulas that's that's all i'm saying with this and so if i plug in boolean values for the a's um [Music] i get exactly the same as i would have gotten before i did the arithmetization because the arithmetization is a faithful simulation i'm should i also say it let's see um what does the or rule now why does the or rule now contain the minus a b term while the previous instance of arithmetization didn't because why remember in the case of branching programs we didn't need the minus a b term um over here and that was because we could argue that it was a disjoint or um in the case of the branching programs i don't want to get confusing by trying to explain why that was but in that earlier case we never had took an or of two ones it was an or of zero zero possibly zero one or possibly one zero and so therefore we never had to deal with the case when we had an or of a one one and here we can have that so we have to subtract off that a b term because otherwise we'd have if we just had a plus b then when the one one case we would end up with a two and that would not be a faithful stimulation of the or operation because one or one should be just one not two so a good this is a good question here do all the numbers need to be zeros and ones i'm not sure how negation would work would work with larger numbers so this is um the negation is just you just blindly follow it even though we're going to be plugging in non-boolean values um [Music] you know it's gonna be one minus a seven so you're gonna get minus six you have to do that mod p so whatever mod q so whatever whatever that value you get but um you can no longer think about it as negation in the in the in the former sense now it just becomes a formal thing um you're you're just plugging along doing what the polynomial says numbers are coming out you think you know this is just nonsense but the thing is it's going to have a meaning that's going to be useful to us that's that's what this protocol is going to show yeah so um you can't think about it as negation anymore it's just the negation becomes one minus x in the power in the arithmetized world and you just have to live with that let's see um okay uh another question here if all the fee are equivalent for boolean inputs in the in the check-in um so this is back into this check-in here so if all of the uh p yeah you know so the question is why if they're all equivalent in the boolean case uh why is only a correct um because this is i define piece of fee in a particular way and so this was the value you got if you follow the way i define piece of piece of fee the others would work they just weren't the way i defined it um okay uh any other questions here we should probably move on okay can arithmetization be used in other contexts um uh i often i don't know i there are these two cases where arithmetization works whether there are other cases too i'm actually not sure okay so let's move on so uh our our but our timer is up the candle is burned down okay so this was um okay here we go this is the real protocol um so i'm going to present it to you the way i did before let's think about it with the case first where the input is in the language and we have an honest brewer um so we start off the same way the approver sends fee it sends number fee which in the old sense was the number of satisfying assignments it actually still is because you know since we're not presetting anything there's no non-booleans um in the picture yet so this is going to be the same value as before the verifier checks that k equals number phase so you have to that's why we have to have the big enough field there so that we can um represent numbers up to the number of potential numbers satisfying assignments but that's a side note so but anyway p sends this is exactly what we did before no change the number of satisfying assignments feel like now let's just see let's remember and this is this is one of those cases where not having a big blackboard is hampers us so i'm just going to remind you what we did last time but i'm going to change this so remember before p said sent an unpacked at one level sent the number of satisfying assignments said number uh fee of zero a number fee of one and then v did that check to justify the previous value which the verifier doesn't necessarily trust okay fasten your seat belts everybody this is the whole proof in the next line okay so but it's a doozy um all right is going to send phi of z as a polynomial in z it's going to send just a single object but that object is an entire polynomial and the way it's going to send that is by sending the coefficients of that polynomial okay so let's uh let's um that statement um so first of all um let's understand the value of doing that so if i can send the entire polynomial fee sub z represent that as a polynomial i can plug in 0 and 1 into that polynomial and allow me allow the verifier to do the check that it needs to do to con to um demonstrate that uh number fee is correct so it's going to check that number fee is a number fee of zero plus number fee of one but instead of getting those values directly from the prover it's going to get take that polynomial it got and evaluate that polynomial at zero and one okay so let and just to remember let's go back and remember how we defined uh defined uh number fee to make sure that we understand what it means to have a polynomial here so remember here we're just taking the very first value you could put you are okay with putting a constant 0 or 1 and then adding up over all possible ex extensions all possible boolean extensions to that um and maybe it's okay to put in a non-boolean value here like seven and now you take the remaining variables and it and assign them zeros and ones and all possibilities and add it up now i'm going to do something even a little wilder i'm going to put in a variable for a1 some you know symbolic if you want symbolic value so i'm going to put in a value z for a1 so now i plug in z for a1 here and a2 through am are going to be zeros and ones in all possible ways so i just get a polynomial in z the other variables have been get assigned and added up over the various boolean assignments and now i get some polynomial so i get some expression in z that's just going to be a single variable polynomial okay you whose degree is it going to be at most the degree of number fee so it's degree is not going to be too big um so it sends the coefficient so the degree of that is not too big so there are not too many coefficients to send um so the coefficients are in terms of the xi's no i'm not sure what the mean the coefficients are not in terms the x i's are gone at this point the x i's we've added up the x i's being assigned to zeros and ones in all possible ways so there are no other variables left there's only z um so i'm gonna do the same protocol in a more pictorial way in a minute um so you're gonna see this whole thing twice uh but try to get it you'll have two chances to get this try to get it you know try hard each time um so it's got sensi as a polynomial in z now that's going to be enough for me to figure out which number fee of zero and number fee is of one is because i plug it in for zero and one for for z but now i can figure out what number fee of two is also because i can plug two in for z or number fee of seven i plug seven in for z okay so let's stop here and let's see on other other questions so the so is the size of number fee i don't understand the so this question about the size of number fee um is it is it 2 to the n no it's not 2 to the m because the degree of that polynomial uh number phi of z i mean you know it's a very large expression if you want to initially you know yes writing that it's going to be an exponentially big sum but the prover adds it all up for you and you're just going to have at most a small number of coefficients because the polynomial is only of a certain degree and a polynomial in one variable of degree d has the most d or d plus one coefficients to worry about so it's not that many coefficients as an expression so um shouldn't the summation take 2 to the m time i'm not caring about the prover's time the prover has a lot of work to do but the prover prov sends fee of z so uh the prover yes the proofer has a an exponential job i don't care the verifier always needs to be able to check it in polynomial time and that checking is gonna well we'll have to see how does the verifier know that that polynomial was right that's a question you may maybe you should be asking um yeah okay i'm getting lots of questions about how much time the prover needs to take yeah the proof is going to have to spend exponential time to figure out that polynomial but that's all right we're not we don't care about the provers time um yeah so the summation here is going to be adding up polynomials that is correct i'm happy to spend time because really here this is the whole proof you have to understand well we have to understand why this works but um we kind of understand half of it because knowing that polynomial is enough to you know if you could certify that that was the correct polynomial for a number fee of z then we can use that polynomial to to confirm the previous value what number fee was because you just plug in zeros and ones for this for z and you add it up but now how are we going to justify that the polynomial is correct because this looks like even a worse job now we have a whole bunch of coefficients and have to make sure all of those coefficients are right and so instead of just two values now we have like d values where d is the degree of that polynomial which could be at most like the length of the formula um uh so here is the next idea um so the prover needs to show that phi of z is correct okay um the way it's going to do that let's say so even before before we do that so fee of z is going to be some polynomial um now the prover may be lying maybe sending the wrong polynomial how does the prover convince the verifier that the power that that polynomial is the right polynomial well that seems like a tough job so what it's going to do is remember that the um there is so there you know there is there is a correct polynomial that you would get by plugging into this expression for the for the correct value so there's some correct polynomial the prover may be sending some some incorrect polynomial but now those so now we have the correct polynomial and the possibly incorrect polynomial which and the point is those two can only agree in a small number of places by that fact that we proved a couple of lectures back regarding polynomials so two different polynomials can agree only rarely so what we're going to do the way the prover is going to justify that this polynomial was the correct one is by evaluating it at a random place and then demonstrating that that value you get is a correct value if the polynomial was the wrong polynomial then evaluating it at a random place is probably going to disagree with the correct polynomial at that place because they can only agree rarely so the prover is going to demonstrate that by evaluating that polynomial at a random place that value you get is going to be the correct value and it's going to continue to do that in the way using the same protocol as we'll see so that's where we're going so to in order to show that figure z is correct the verifier now gets to pick a random value in the field and the prover is going to show that evaluating that polynomial at r1 is correct remember this looks a lot like what we had from before where we were val showing that number fee of zero is correct the number fee of one is correct now we're trying to show that number fee of r1 this random value from the field is correct so the way we're going to do that is now by unpacking it one level down we're going to be using those identity that identity by because this value here is going to be equal to um number fee of r1 comma 0 plus number fee of r1 comma 1. so the way but we don't want to send both of those so we're going to send them combined into a polynomial of number fee of r1 of z as a polynomial in z this is the new polynomial in z okay so now if you understood the previous line then hopefully this one won't be too hard to swallow because now we're going to check um the identity but here by evaluating the polynomial again but one level at the next level okay so this is this is um uh perhaps a good place to uh to take questions because this is this is the heart this is really what i spent all the time setting things up for so that you would be ready to get this thing hopefully without you know and hopefully get be able to appreciate it and understand okay so um so let's let i'm not getting questions let's let's move on a little further so now in order so the pollen again the approver has sent this polynomial at the next in stage two um now we the verifier needs to be sure that that polynomial is correct so it's going to evaluate um that polynomial that new polynomial um at a random location um so by picking a random value r2 in in um in the field uh and now it needs to show that this value is is correct um because if that polynomial had been the wrong polynomial it disagreed with the correct polynomial almost everywhere and by picking a random place it's probably not going to be the right value and we'd s all of the values have been picked and so we have one last value um uh to to select a zero and one this corresponds to the nth you know if you it would be great if i could put both pictures on um on your screen but i can't um so this very much corresponds to what happened in the exponential protocol but just along you know sort of this arithmetic arithmetized one single path so uh it checks that the previous value is is correct in terms of expanding it with zero and one but again the zero and one comes from evaluating the polynomial um and now the verifier needs to be convinced that that polynomial was right so it picks a random value but now it doesn't rely on the prover anymore it's going to see whether that that assignment that it gets by evaluating the polynomial with that random value rm plugged in is the same as what i get by evaluating the polynomial for the formula itself that the verifier can do directly because this is now a polynomial now just plugging into the formula and using the arithmetization to get a value out okay so this was the last line of the identity okay we had those two identity those two identities so this is the second identity and we have to check that this is correct okay so uh so i'm gonna describe show this to you in a picture uh not sure it'll help if you're if you're confused but why don't we take some questions on this so as i said i'm going to give you two chances to understand this um because i know it's tough this is especially with the constraints of zoom this is a particularly challenging idea to explain okay so let's see so the benefit of this approach is that the approver only sends one item for each depth level instead of multiple items that's right but that one item is the polynomial so that that captures all of the values for the entire field but taking advantage of the arithmetization that one polynomial you know us has a lot of information in it and what's nice is that you can check that polynomial by just evaluating it at random one random place you can check that that polynomial is correct um okay um so where does so i'm getting another question here where does this come from here if we we checks that this here so this where does this so you have to look to understand why where this is coming from you have to we're at the end round now so you have to look back like at round two v has to check that fee of r1 which comes from the end of the first round so this checks that this fee of r1 is correct because that was where that was how we justified the polynomial with just a single variable the the very first polynomial is correct you know a little hard to say but this comes from the previous round this this guy here um okay so this is the polynomial for the current round this is the value from the previous round all right more questions so so why doesn't this run for exponential time another question i'm getting doesn't v need to check twice at each layer yes if the the verifier needs to check um gets two values but those two values come from the one polynomial so there's no blow up anymore you know those two values maybe you'll see it in the picture that i'm going to show so maybe just hold that question and maybe this will become clearer in the in the diagram so another question does this work because the polynomial encodes kind of encodes all the possible values together i think that's sort of true that sort of mixes them all together into one object then you have to check that one object which can be done with a sort of random probing of it um okay so so this is another good question that we'll see explained in the next slide so uh so similarly in attempt one the prover can keep lying by by picking polynomials um in rounds one you know by continuing to pick polynomials by lying about the polynomials but eventually it's going to get caught because this value is going to be the wrong value you know if the polynomial in the previous stage and the m minus f you know if it's a polynomial that the prover sent in the m state is the wrong polynomial then you evaluate it you're going to get the wrong value probably um and so then that wrong value is not going to match the correct value which is you can read you off yourself by reading the formula okay i think we should need to move on to the next slide um all right so same proof version two but looks different um again the input is that here's what the approver sends here is what the verifier sends i'm gonna i sort of whimsically designed this as a uh as a telephone chat where they're sending each method messages through uh messaging okay so the prover sends uh the number fee to start off with and then off on the side these are the checks that the verifier is going to be doing so here in our first round of the chat the approver is going to send fee of z remember this is just a a polynomial in not too many coefficients so it's a polynomial in one variable the degree is small so there are not too many coefficients here you know so this is uh so pretending this is what it might look like and then the verify so from that polynomial the verifier can plug in zero and one and see that the adds up um now the verifier to check that this polynomial is correct it picks a random value to evaluate this polynomial on um uh and so now it's going to have to check that this is correct so this is not nothing to check you're just writing this down in anticipation of the next check now the prover to justify that that this value is right that that this polynomial is right so we evaluate okay doesn't say that to prove in order to check that this value is right is going to send the polynomial for the next level um now we can from that we can plug in zero and one for z see if that adds up and now to be sure that this polynomial is right um we evaluate it at a random place calculate that value and then um uh have to have to see that this value is correct so now we expanded one level down further we pick a we we take a polynomial for the next variable and we see that it adds up okay i i'm not i'm not sure what whether this is helping or not um but we keep doing that until we get to the very last round uh where the prover's sending a polynomial make sure that this adds up correctly um and the verifier to be see that this polynomial is right picks a random value and uh evaluates it and now checks that this agrees with the formula because we've now assigned all of the variables and the then we can then we can check this number fee directly in terms of the fee um because they have to agree okay and so the verify would accept if everything checks out let's see what happens so this answer will answer some questions um why don't i go walk through what happens if um the input was wrong and we'll we'll see how the verifier is likely to catch the approver but not guaranteed to catch the approver in this case um so if k was correct the verifier will accept with the honest prover but if k was wrong so i'm going to again indicate the wrong values in red um i'm going to show you that the verifiers is almost certainly going to accept but not guaranteed so uh did i say that wrong so if k is wrong the verifier is going to probably reject but it's not guaranteed to reject so um first of all if the does not lie does not send the wrong value for a number fee the verifier is certainly going to reject because it's not going to be get any quality there um so the prover has to lie you know say you know um you know if k was 99 but the real value was 100 the approver if it says 100 the verifier is going to reject immediately so the verifies you know the proof is going to say well let's let's see what what the approver can do to make the verifier uh hopefully accept from the approver's standpoint so the proof is going to send 99. well the verifier says okay 99 fine uh convince me so the program now um you know one of these two has is going to be wrong uh has to be because the two correct values can't add up to the wrong value so one of these is wrong so that means the prover had to send the wrong polynomial because the correct polynomial would evaluate the correct answers here so the prover had to send the wrong polynomial so now when we evaluate it at a random place chances are this is going to be the wrong this is not going to be the same value that the correct polynomial would have given you the prover could get lucky we could have verified it might have just happened to pick a place with a correct polynomial and the incorrect polynomial agree and that place the approval think huh i'm saved now i can act like the honest prover from this point on and you know the verifier will never catch me you know i said a little bit analogous to the situation maybe you know you know i'm trying to see if you really studied the whole course so i'm giving you an exam but by picking sort of random places there but maybe you just studied you know a few facts from the from the course you might get lucky i might happen to ask just about those facts and then you give the appearance of having studied everything but you really didn't so here the approver might send the wrong polynomial but the verifier just queries that at the place where it happens to agree with the correct polynomial and the verb just gets lucky and the verifier is going to accept in that case but there are very few of those so that's why the prover is almost certainly to be caught if it tries to lie but not guaranteed um so again so just tracing this down uh if this was a lie then one of those two has to be a lie so therefore the next polynomial has to be a lie and so we continue so then the next value is almost certainly going to be a lie not guaranteed and so then one of those two values has to be a lot at least one has to be a lie therefore the polynomial has to be a lie and so on um uh until uh you know unless the approver got lucky along the way somewhere which is very unlikely even though it has several opportunities you know we've arranged ranges so that the chance of getting lucky is tiny at each stage so even though he has a few chances there's still going to be a tiny chance that you're going to get lucky somewhere and so this is wrong then chances are that's wrong and so therefore this is going to be a disagreement and the verifier at that point when it doesn't agree it's going to reject unless the people got lucky somewhere along the way which is unlikely okay so uh i don't know if you had so that's my all i was going to say about this proof uh i don't know if you had any questions on it but let's just see okay so [Music] uh do we have any questions i can answer how the approver gets how how does approver get number how does the prover get number fee of z um so you have to you know why is number fee of z have no other variables you have to go back and look at the the definition of number fee of number fee of a because you add up over all the other variables so now we're pick plugging in instead of a plugging a variable for that but you're still adding up over the other variables so this is a very column this is a function in just one variable which is about who can because it's you know it was original original thing was a polynomial so so this is also going to be following um i think we're starting to run low on time so this is our very last check-in for the semester here so of course there's one natural question to ask you all and for our very last check-in as we're in our last couple of minutes of the course or the least of the lectures does p equal np what do you think will maybe pb equal np be solved by a deep learning algorithm or maybe we'll never prove it give me your best guess okay we're kind of running out of time so let's not think too hard here um another five seconds all right ending polling uh i'll share that with you oh yeah i did share uh so what what do we get d here we will prove it in somewhere between 20 and 100 years from now that's the seems to be the majority opinion uh i don't know i hope it'll be sooner than that because i'd like to see the answer but uh we don't know uh uh yeah if you can prove peter from np yeah yeah i'll give you an a plus you won't have to take the final but you better be sure you're right um all right so what that is our quick review we finished number sat in ip and therefore that co-np is a subset of ip um if you're interested in further pursuit of this material i got a couple of questions on that these are some courses you may want to look at um i know i checked with um ryan williams he's planning to teach advanced complexity uh fall 2021 so um uh that's we're going to be one the most natural follow-on subject to this one is the crypto classes also are kind of make use of some of the same ideas and there's of course also randomness computation that ronit rubenfeld teaches i don't know if i didn't check with her i don't sure the next time she's going to be teaching that um and uh good luck on the final and best wishes so um and i'm gonna have office hours so if you have any questions uh you know happy to uh answer those but otherwise see you all good luck thank you for the comments yeah i enjoyed having you all as students it was it was uh it was a fun time a lot of work but it was a fun time i've always been intrigued by p the p versus np problem and i proved a kind of a i proved the exponential complexity of computing the parity function in a certain weak model of computation so parity function is very obviously very trivial function um but the for the parity function if you can't count whatever that means but there's a there is a model you can kind of set up but you can't count then parity requires exponential complexity and surprisingly not easy to prove uh but that's probably the theorem that i'm most known for anyway but that would be a topic for another day um another question why not include my hills the my hill and the road theorem seems i don't know that's a theorem about finite automata and all of those ways of characterizing the regular languages that seems kind of a tactic technical theorem i don't don't see much point in covering it and another question that some of my colleagues ask me is why don't i have rice's theorem which is sort of provides a kind of a machine for proving undecidability and uh i don't know i think that you can use rice's theorem without understanding how to prove undecidability it becomes sort of uh it's like a it's like checking off checking off a box checking some boxes and then you get conclude something's undecidable i'd rather have somebody understand it rather than just be able to use some powerful tool um can we understand that proof of the num the proof about the parity function uh that i just alluded to that's super hard you can with the knowledge from this class i think you can um the the that theorem uh relies on a certain technique which we didn't cover uh called the probabilistic method which is a kind of an amazing method uh not hard to explain but basically you show that something exists by showing that the probability that a random object has the property you're looking for is more than zero um and so therefore the thing that you're looking for that has that property has to exist um there are lots of examples of that these days but it's it's kind of an amazing method so use that method do i think quantum computing can solve useful problems beyond the capability of classical computers i have no idea whether one can really build a quantum computer it seems to be always 20 years off at least to doing one that factors and i've been literally uh i remember people 20 years ago saying it's 20 years off so uh i don't think it's converging um i i'm skeptical that they'll ever build a chronic computer that can factor i'll go out on a limb and say that but that's controversial um and whether it can solve other useful problems i'm not sure whether useful problems are there well i guess they're simulating quantum systems so maybe that that might be possible um all right i think i'm gonna i'm gonna end this now but thank you everybody take care bye you 4 00:00:28,070 --> 00:00:31,750 5 00:00:31,750 --> 00:00:33,510 6 00:00:33,510 --> 00:00:33,520 7 00:00:33,520 --> 00:00:34,950 8 00:00:34,950 --> 00:00:38,709 9 00:00:38,709 --> 00:00:41,030 10 00:00:41,030 --> 00:00:42,869 11 00:00:42,869 --> 00:00:46,150 12 00:00:46,150 --> 00:00:48,150 13 00:00:48,150 --> 00:00:50,150 14 00:00:50,150 --> 00:00:52,630 15 00:00:52,630 --> 00:00:54,630 16 00:00:54,630 --> 00:00:56,869 17 00:00:56,869 --> 00:00:59,910 18 00:00:59,910 --> 00:01:04,149 19 00:01:04,149 --> 00:01:06,070 20 00:01:06,070 --> 00:01:10,310 21 00:01:10,310 --> 00:01:10,320 22 00:01:10,320 --> 00:01:11,270 23 00:01:11,270 --> 00:01:13,270 24 00:01:13,270 --> 00:01:13,280 25 00:01:13,280 --> 00:01:14,070 26 00:01:14,070 --> 00:01:17,910 27 00:01:17,910 --> 00:01:19,429 28 00:01:19,429 --> 00:01:20,950 29 00:01:20,950 --> 00:01:23,190 30 00:01:23,190 --> 00:01:25,590 31 00:01:25,590 --> 00:01:28,710 32 00:01:28,710 --> 00:01:30,550 33 00:01:30,550 --> 00:01:32,469 34 00:01:32,469 --> 00:01:34,390 35 00:01:34,390 --> 00:01:34,400 36 00:01:34,400 --> 00:01:35,429 37 00:01:35,429 --> 00:01:38,149 38 00:01:38,149 --> 00:01:38,159 39 00:01:38,159 --> 00:01:39,670 40 00:01:39,670 --> 00:01:41,190 41 00:01:41,190 --> 00:01:43,830 42 00:01:43,830 --> 00:01:46,230 43 00:01:46,230 --> 00:01:48,230 44 00:01:48,230 --> 00:01:50,870 45 00:01:50,870 --> 00:01:52,789 46 00:01:52,789 --> 00:01:54,600 47 00:01:54,600 --> 00:01:54,610 48 00:01:54,610 --> 00:01:56,069 49 00:01:56,069 --> 00:01:56,079 50 00:01:56,079 --> 00:01:57,270 51 00:01:57,270 --> 00:01:57,280 52 00:01:57,280 --> 00:01:59,270 53 00:01:59,270 --> 00:02:01,749 54 00:02:01,749 --> 00:02:03,429 55 00:02:03,429 --> 00:02:05,030 56 00:02:05,030 --> 00:02:07,510 57 00:02:07,510 --> 00:02:11,110 58 00:02:11,110 --> 00:02:11,120 59 00:02:11,120 --> 00:02:13,589 60 00:02:13,589 --> 00:02:14,630 61 00:02:14,630 --> 00:02:14,640 62 00:02:14,640 --> 00:02:15,830 63 00:02:15,830 --> 00:02:18,790 64 00:02:18,790 --> 00:02:23,270 65 00:02:23,270 --> 00:02:26,390 66 00:02:26,390 --> 00:02:28,390 67 00:02:28,390 --> 00:02:30,550 68 00:02:30,550 --> 00:02:34,070 69 00:02:34,070 --> 00:02:35,990 70 00:02:35,990 --> 00:02:38,710 71 00:02:38,710 --> 00:02:40,390 72 00:02:40,390 --> 00:02:42,949 73 00:02:42,949 --> 00:02:44,150 74 00:02:44,150 --> 00:02:44,160 75 00:02:44,160 --> 00:02:45,670 76 00:02:45,670 --> 00:02:48,150 77 00:02:48,150 --> 00:02:50,550 78 00:02:50,550 --> 00:02:53,110 79 00:02:53,110 --> 00:02:56,949 80 00:02:56,949 --> 00:02:59,030 81 00:02:59,030 --> 00:03:00,790 82 00:03:00,790 --> 00:03:03,190 83 00:03:03,190 --> 00:03:05,270 84 00:03:05,270 --> 00:03:09,509 85 00:03:09,509 --> 00:03:09,519 86 00:03:09,519 --> 00:03:10,869 87 00:03:10,869 --> 00:03:10,879 88 00:03:10,879 --> 00:03:12,869 89 00:03:12,869 --> 00:03:14,630 90 00:03:14,630 --> 00:03:14,640 91 00:03:14,640 --> 00:03:15,430 92 00:03:15,430 --> 00:03:18,149 93 00:03:18,149 --> 00:03:20,550 94 00:03:20,550 --> 00:03:20,560 95 00:03:20,560 --> 00:03:22,390 96 00:03:22,390 --> 00:03:24,869 97 00:03:24,869 --> 00:03:26,470 98 00:03:26,470 --> 00:03:28,949 99 00:03:28,949 --> 00:03:30,789 100 00:03:30,789 --> 00:03:33,110 101 00:03:33,110 --> 00:03:34,710 102 00:03:34,710 --> 00:03:36,390 103 00:03:36,390 --> 00:03:36,400 104 00:03:36,400 --> 00:03:37,430 105 00:03:37,430 --> 00:03:39,270 106 00:03:39,270 --> 00:03:41,830 107 00:03:41,830 --> 00:03:45,750 108 00:03:45,750 --> 00:03:49,190 109 00:03:49,190 --> 00:03:50,630 110 00:03:50,630 --> 00:03:52,070 111 00:03:52,070 --> 00:03:53,990 112 00:03:53,990 --> 00:03:56,949 113 00:03:56,949 --> 00:03:56,959 114 00:03:56,959 --> 00:03:58,789 115 00:03:58,789 --> 00:04:00,869 116 00:04:00,869 --> 00:04:02,630 117 00:04:02,630 --> 00:04:04,710 118 00:04:04,710 --> 00:04:07,030 119 00:04:07,030 --> 00:04:09,110 120 00:04:09,110 --> 00:04:11,190 121 00:04:11,190 --> 00:04:13,509 122 00:04:13,509 --> 00:04:15,350 123 00:04:15,350 --> 00:04:15,360 124 00:04:15,360 --> 00:04:18,229 125 00:04:18,229 --> 00:04:18,239 126 00:04:18,239 --> 00:04:19,270 127 00:04:19,270 --> 00:04:19,280 128 00:04:19,280 --> 00:04:20,789 129 00:04:20,789 --> 00:04:23,030 130 00:04:23,030 --> 00:04:25,350 131 00:04:25,350 --> 00:04:27,909 132 00:04:27,909 --> 00:04:29,830 133 00:04:29,830 --> 00:04:31,350 134 00:04:31,350 --> 00:04:34,070 135 00:04:34,070 --> 00:04:36,310 136 00:04:36,310 --> 00:04:37,990 137 00:04:37,990 --> 00:04:40,390 138 00:04:40,390 --> 00:04:42,230 139 00:04:42,230 --> 00:04:44,310 140 00:04:44,310 --> 00:04:47,830 141 00:04:47,830 --> 00:04:50,310 142 00:04:50,310 --> 00:04:52,469 143 00:04:52,469 --> 00:04:53,909 144 00:04:53,909 --> 00:04:57,110 145 00:04:57,110 --> 00:05:00,070 146 00:05:00,070 --> 00:05:02,230 147 00:05:02,230 --> 00:05:04,150 148 00:05:04,150 --> 00:05:06,710 149 00:05:06,710 --> 00:05:08,870 150 00:05:08,870 --> 00:05:10,950 151 00:05:10,950 --> 00:05:13,110 152 00:05:13,110 --> 00:05:14,870 153 00:05:14,870 --> 00:05:18,310 154 00:05:18,310 --> 00:05:20,790 155 00:05:20,790 --> 00:05:22,469 156 00:05:22,469 --> 00:05:25,110 157 00:05:25,110 --> 00:05:29,670 158 00:05:29,670 --> 00:05:29,680 159 00:05:29,680 --> 00:05:30,710 160 00:05:30,710 --> 00:05:30,720 161 00:05:30,720 --> 00:05:31,030 162 00:05:31,030 --> 00:05:31,040 163 00:05:31,040 --> 00:05:32,790 164 00:05:32,790 --> 00:05:32,800 165 00:05:32,800 --> 00:05:34,710 166 00:05:34,710 --> 00:05:36,390 167 00:05:36,390 --> 00:05:38,870 168 00:05:38,870 --> 00:05:40,790 169 00:05:40,790 --> 00:05:42,469 170 00:05:42,469 --> 00:05:45,110 171 00:05:45,110 --> 00:05:45,120 172 00:05:45,120 --> 00:05:46,070 173 00:05:46,070 --> 00:05:48,310 174 00:05:48,310 --> 00:05:50,469 175 00:05:50,469 --> 00:05:52,469 176 00:05:52,469 --> 00:05:54,710 177 00:05:54,710 --> 00:05:56,550 178 00:05:56,550 --> 00:05:57,909 179 00:05:57,909 --> 00:05:59,830 180 00:05:59,830 --> 00:06:02,150 181 00:06:02,150 --> 00:06:05,510 182 00:06:05,510 --> 00:06:07,189 183 00:06:07,189 --> 00:06:08,710 184 00:06:08,710 --> 00:06:10,070 185 00:06:10,070 --> 00:06:12,309 186 00:06:12,309 --> 00:06:13,990 187 00:06:13,990 --> 00:06:15,350 188 00:06:15,350 --> 00:06:17,270 189 00:06:17,270 --> 00:06:17,280 190 00:06:17,280 --> 00:06:18,830 191 00:06:18,830 --> 00:06:21,749 192 00:06:21,749 --> 00:06:23,189 193 00:06:23,189 --> 00:06:24,629 194 00:06:24,629 --> 00:06:26,790 195 00:06:26,790 --> 00:06:27,749 196 00:06:27,749 --> 00:06:31,350 197 00:06:31,350 --> 00:06:33,749 198 00:06:33,749 --> 00:06:36,469 199 00:06:36,469 --> 00:06:38,950 200 00:06:38,950 --> 00:06:42,950 201 00:06:42,950 --> 00:06:45,510 202 00:06:45,510 --> 00:06:47,830 203 00:06:47,830 --> 00:06:50,309 204 00:06:50,309 --> 00:06:52,870 205 00:06:52,870 --> 00:06:55,270 206 00:06:55,270 --> 00:06:56,550 207 00:06:56,550 --> 00:06:59,270 208 00:06:59,270 --> 00:07:00,950 209 00:07:00,950 --> 00:07:03,749 210 00:07:03,749 --> 00:07:06,629 211 00:07:06,629 --> 00:07:06,639 212 00:07:06,639 --> 00:07:08,550 213 00:07:08,550 --> 00:07:12,230 214 00:07:12,230 --> 00:07:14,950 215 00:07:14,950 --> 00:07:16,390 216 00:07:16,390 --> 00:07:17,830 217 00:07:17,830 --> 00:07:19,990 218 00:07:19,990 --> 00:07:21,749 219 00:07:21,749 --> 00:07:25,189 220 00:07:25,189 --> 00:07:26,550 221 00:07:26,550 --> 00:07:27,830 222 00:07:27,830 --> 00:07:29,350 223 00:07:29,350 --> 00:07:30,309 224 00:07:30,309 --> 00:07:32,390 225 00:07:32,390 --> 00:07:34,309 226 00:07:34,309 --> 00:07:36,469 227 00:07:36,469 --> 00:07:41,430 228 00:07:41,430 --> 00:07:42,950 229 00:07:42,950 --> 00:07:46,309 230 00:07:46,309 --> 00:07:49,430 231 00:07:49,430 --> 00:07:51,670 232 00:07:51,670 --> 00:07:51,680 233 00:07:51,680 --> 00:07:52,629 234 00:07:52,629 --> 00:07:55,909 235 00:07:55,909 --> 00:07:57,990 236 00:07:57,990 --> 00:07:59,670 237 00:07:59,670 --> 00:08:02,390 238 00:08:02,390 --> 00:08:03,909 239 00:08:03,909 --> 00:08:03,919 240 00:08:03,919 --> 00:08:05,430 241 00:08:05,430 --> 00:08:06,790 242 00:08:06,790 --> 00:08:06,800 243 00:08:06,800 --> 00:08:07,749 244 00:08:07,749 --> 00:08:09,510 245 00:08:09,510 --> 00:08:11,510 246 00:08:11,510 --> 00:08:11,520 247 00:08:11,520 --> 00:08:12,869 248 00:08:12,869 --> 00:08:14,150 249 00:08:14,150 --> 00:08:14,160 250 00:08:14,160 --> 00:08:15,589 251 00:08:15,589 --> 00:08:15,599 252 00:08:15,599 --> 00:08:17,110 253 00:08:17,110 --> 00:08:20,629 254 00:08:20,629 --> 00:08:22,950 255 00:08:22,950 --> 00:08:25,110 256 00:08:25,110 --> 00:08:27,350 257 00:08:27,350 --> 00:08:29,430 258 00:08:29,430 --> 00:08:33,829 259 00:08:33,829 --> 00:08:37,350 260 00:08:37,350 --> 00:08:39,990 261 00:08:39,990 --> 00:08:41,990 262 00:08:41,990 --> 00:08:44,470 263 00:08:44,470 --> 00:08:46,310 264 00:08:46,310 --> 00:08:47,829 265 00:08:47,829 --> 00:08:47,839 266 00:08:47,839 --> 00:08:49,269 267 00:08:49,269 --> 00:08:51,509 268 00:08:51,509 --> 00:08:51,519 269 00:08:51,519 --> 00:08:52,710 270 00:08:52,710 --> 00:08:55,910 271 00:08:55,910 --> 00:08:55,920 272 00:08:55,920 --> 00:08:57,190 273 00:08:57,190 --> 00:08:59,750 274 00:08:59,750 --> 00:08:59,760 275 00:08:59,760 --> 00:09:00,550 276 00:09:00,550 --> 00:09:02,230 277 00:09:02,230 --> 00:09:05,030 278 00:09:05,030 --> 00:09:07,190 279 00:09:07,190 --> 00:09:07,200 280 00:09:07,200 --> 00:09:08,710 281 00:09:08,710 --> 00:09:08,720 282 00:09:08,720 --> 00:09:09,509 283 00:09:09,509 --> 00:09:13,269 284 00:09:13,269 --> 00:09:15,829 285 00:09:15,829 --> 00:09:17,590 286 00:09:17,590 --> 00:09:19,430 287 00:09:19,430 --> 00:09:21,990 288 00:09:21,990 --> 00:09:24,230 289 00:09:24,230 --> 00:09:26,150 290 00:09:26,150 --> 00:09:29,670 291 00:09:29,670 --> 00:09:30,870 292 00:09:30,870 --> 00:09:30,880 293 00:09:30,880 --> 00:09:32,710 294 00:09:32,710 --> 00:09:32,720 295 00:09:32,720 --> 00:09:34,870 296 00:09:34,870 --> 00:09:37,670 297 00:09:37,670 --> 00:09:39,750 298 00:09:39,750 --> 00:09:42,790 299 00:09:42,790 --> 00:09:44,949 300 00:09:44,949 --> 00:09:46,150 301 00:09:46,150 --> 00:09:48,150 302 00:09:48,150 --> 00:09:50,870 303 00:09:50,870 --> 00:09:54,790 304 00:09:54,790 --> 00:09:56,470 305 00:09:56,470 --> 00:09:58,870 306 00:09:58,870 --> 00:10:02,069 307 00:10:02,069 --> 00:10:02,079 308 00:10:02,079 --> 00:10:03,110 309 00:10:03,110 --> 00:10:05,670 310 00:10:05,670 --> 00:10:07,269 311 00:10:07,269 --> 00:10:07,279 312 00:10:07,279 --> 00:10:09,110 313 00:10:09,110 --> 00:10:11,509 314 00:10:11,509 --> 00:10:13,350 315 00:10:13,350 --> 00:10:16,230 316 00:10:16,230 --> 00:10:16,240 317 00:10:16,240 --> 00:10:17,750 318 00:10:17,750 --> 00:10:20,310 319 00:10:20,310 --> 00:10:23,990 320 00:10:23,990 --> 00:10:25,670 321 00:10:25,670 --> 00:10:28,310 322 00:10:28,310 --> 00:10:30,310 323 00:10:30,310 --> 00:10:33,750 324 00:10:33,750 --> 00:10:35,430 325 00:10:35,430 --> 00:10:38,069 326 00:10:38,069 --> 00:10:38,079 327 00:10:38,079 --> 00:10:38,870 328 00:10:38,870 --> 00:10:40,230 329 00:10:40,230 --> 00:10:42,870 330 00:10:42,870 --> 00:10:44,829 331 00:10:44,829 --> 00:10:49,910 332 00:10:49,910 --> 00:10:49,920 333 00:10:49,920 --> 00:10:52,710 334 00:10:52,710 --> 00:10:54,470 335 00:10:54,470 --> 00:10:55,990 336 00:10:55,990 --> 00:10:58,150 337 00:10:58,150 --> 00:11:00,710 338 00:11:00,710 --> 00:11:02,150 339 00:11:02,150 --> 00:11:03,509 340 00:11:03,509 --> 00:11:03,519 341 00:11:03,519 --> 00:11:04,949 342 00:11:04,949 --> 00:11:06,870 343 00:11:06,870 --> 00:11:09,590 344 00:11:09,590 --> 00:11:09,600 345 00:11:09,600 --> 00:11:10,949 346 00:11:10,949 --> 00:11:12,550 347 00:11:12,550 --> 00:11:15,190 348 00:11:15,190 --> 00:11:17,030 349 00:11:17,030 --> 00:11:18,949 350 00:11:18,949 --> 00:11:21,590 351 00:11:21,590 --> 00:11:22,710 352 00:11:22,710 --> 00:11:25,590 353 00:11:25,590 --> 00:11:25,600 354 00:11:25,600 --> 00:11:27,110 355 00:11:27,110 --> 00:11:29,670 356 00:11:29,670 --> 00:11:32,069 357 00:11:32,069 --> 00:11:33,350 358 00:11:33,350 --> 00:11:35,030 359 00:11:35,030 --> 00:11:37,110 360 00:11:37,110 --> 00:11:39,910 361 00:11:39,910 --> 00:11:41,670 362 00:11:41,670 --> 00:11:45,509 363 00:11:45,509 --> 00:11:49,509 364 00:11:49,509 --> 00:11:52,629 365 00:11:52,629 --> 00:11:54,310 366 00:11:54,310 --> 00:11:57,190 367 00:11:57,190 --> 00:11:57,200 368 00:11:57,200 --> 00:11:59,030 369 00:11:59,030 --> 00:11:59,040 370 00:11:59,040 --> 00:12:00,389 371 00:12:00,389 --> 00:12:02,230 372 00:12:02,230 --> 00:12:04,710 373 00:12:04,710 --> 00:12:07,509 374 00:12:07,509 --> 00:12:10,230 375 00:12:10,230 --> 00:12:12,870 376 00:12:12,870 --> 00:12:14,310 377 00:12:14,310 --> 00:12:16,949 378 00:12:16,949 --> 00:12:18,150 379 00:12:18,150 --> 00:12:20,790 380 00:12:20,790 --> 00:12:23,030 381 00:12:23,030 --> 00:12:25,269 382 00:12:25,269 --> 00:12:27,910 383 00:12:27,910 --> 00:12:27,920 384 00:12:27,920 --> 00:12:28,870 385 00:12:28,870 --> 00:12:30,629 386 00:12:30,629 --> 00:12:32,550 387 00:12:32,550 --> 00:12:34,790 388 00:12:34,790 --> 00:12:37,030 389 00:12:37,030 --> 00:12:39,030 390 00:12:39,030 --> 00:12:42,389 391 00:12:42,389 --> 00:12:44,150 392 00:12:44,150 --> 00:12:46,069 393 00:12:46,069 --> 00:12:46,079 394 00:12:46,079 --> 00:12:47,670 395 00:12:47,670 --> 00:12:49,430 396 00:12:49,430 --> 00:12:49,440 397 00:12:49,440 --> 00:12:51,350 398 00:12:51,350 --> 00:12:53,430 399 00:12:53,430 --> 00:12:53,440 400 00:12:53,440 --> 00:12:54,230 401 00:12:54,230 --> 00:12:54,240 402 00:12:54,240 --> 00:12:55,190 403 00:12:55,190 --> 00:12:56,629 404 00:12:56,629 --> 00:12:56,639 405 00:12:56,639 --> 00:12:57,910 406 00:12:57,910 --> 00:12:59,910 407 00:12:59,910 --> 00:13:02,949 408 00:13:02,949 --> 00:13:07,269 409 00:13:07,269 --> 00:13:07,279 410 00:13:07,279 --> 00:13:08,870 411 00:13:08,870 --> 00:13:11,269 412 00:13:11,269 --> 00:13:13,030 413 00:13:13,030 --> 00:13:14,069 414 00:13:14,069 --> 00:13:15,430 415 00:13:15,430 --> 00:13:18,710 416 00:13:18,710 --> 00:13:21,350 417 00:13:21,350 --> 00:13:23,190 418 00:13:23,190 --> 00:13:26,550 419 00:13:26,550 --> 00:13:28,310 420 00:13:28,310 --> 00:13:30,069 421 00:13:30,069 --> 00:13:33,030 422 00:13:33,030 --> 00:13:33,040 423 00:13:33,040 --> 00:13:36,470 424 00:13:36,470 --> 00:13:38,870 425 00:13:38,870 --> 00:13:40,949 426 00:13:40,949 --> 00:13:43,670 427 00:13:43,670 --> 00:13:45,350 428 00:13:45,350 --> 00:13:45,360 429 00:13:45,360 --> 00:13:46,829 430 00:13:46,829 --> 00:13:49,030 431 00:13:49,030 --> 00:13:50,870 432 00:13:50,870 --> 00:13:53,269 433 00:13:53,269 --> 00:13:58,949 434 00:13:58,949 --> 00:14:00,949 435 00:14:00,949 --> 00:14:03,110 436 00:14:03,110 --> 00:14:04,790 437 00:14:04,790 --> 00:14:06,069 438 00:14:06,069 --> 00:14:09,030 439 00:14:09,030 --> 00:14:10,949 440 00:14:10,949 --> 00:14:13,030 441 00:14:13,030 --> 00:14:14,629 442 00:14:14,629 --> 00:14:17,030 443 00:14:17,030 --> 00:14:21,189 444 00:14:21,189 --> 00:14:22,870 445 00:14:22,870 --> 00:14:23,750 446 00:14:23,750 --> 00:14:25,509 447 00:14:25,509 --> 00:14:27,829 448 00:14:27,829 --> 00:14:29,189 449 00:14:29,189 --> 00:14:31,110 450 00:14:31,110 --> 00:14:32,389 451 00:14:32,389 --> 00:14:34,629 452 00:14:34,629 --> 00:14:36,949 453 00:14:36,949 --> 00:14:38,949 454 00:14:38,949 --> 00:14:40,550 455 00:14:40,550 --> 00:14:41,910 456 00:14:41,910 --> 00:14:45,350 457 00:14:45,350 --> 00:14:45,360 458 00:14:45,360 --> 00:14:47,030 459 00:14:47,030 --> 00:14:48,310 460 00:14:48,310 --> 00:14:50,389 461 00:14:50,389 --> 00:14:51,750 462 00:14:51,750 --> 00:14:53,910 463 00:14:53,910 --> 00:14:55,590 464 00:14:55,590 --> 00:14:58,069 465 00:14:58,069 --> 00:15:01,509 466 00:15:01,509 --> 00:15:05,750 467 00:15:05,750 --> 00:15:05,760 468 00:15:05,760 --> 00:15:06,870 469 00:15:06,870 --> 00:15:12,230 470 00:15:12,230 --> 00:15:13,189 471 00:15:13,189 --> 00:15:14,710 472 00:15:14,710 --> 00:15:18,230 473 00:15:18,230 --> 00:15:18,240 474 00:15:18,240 --> 00:15:20,389 475 00:15:20,389 --> 00:15:20,399 476 00:15:20,399 --> 00:15:21,990 477 00:15:21,990 --> 00:15:24,230 478 00:15:24,230 --> 00:15:24,240 479 00:15:24,240 --> 00:15:25,509 480 00:15:25,509 --> 00:15:28,150 481 00:15:28,150 --> 00:15:30,150 482 00:15:30,150 --> 00:15:31,990 483 00:15:31,990 --> 00:15:32,000 484 00:15:32,000 --> 00:15:32,790 485 00:15:32,790 --> 00:15:32,800 486 00:15:32,800 --> 00:15:33,509 487 00:15:33,509 --> 00:15:35,509 488 00:15:35,509 --> 00:15:37,269 489 00:15:37,269 --> 00:15:39,509 490 00:15:39,509 --> 00:15:41,670 491 00:15:41,670 --> 00:15:43,590 492 00:15:43,590 --> 00:15:45,670 493 00:15:45,670 --> 00:15:47,030 494 00:15:47,030 --> 00:15:48,949 495 00:15:48,949 --> 00:15:50,949 496 00:15:50,949 --> 00:15:50,959 497 00:15:50,959 --> 00:15:51,990 498 00:15:51,990 --> 00:15:55,110 499 00:15:55,110 --> 00:15:57,590 500 00:15:57,590 --> 00:15:59,590 501 00:15:59,590 --> 00:16:01,670 502 00:16:01,670 --> 00:16:03,509 503 00:16:03,509 --> 00:16:05,110 504 00:16:05,110 --> 00:16:05,120 505 00:16:05,120 --> 00:16:05,910 506 00:16:05,910 --> 00:16:07,829 507 00:16:07,829 --> 00:16:10,230 508 00:16:10,230 --> 00:16:13,430 509 00:16:13,430 --> 00:16:15,670 510 00:16:15,670 --> 00:16:17,509 511 00:16:17,509 --> 00:16:20,230 512 00:16:20,230 --> 00:16:22,310 513 00:16:22,310 --> 00:16:23,829 514 00:16:23,829 --> 00:16:26,230 515 00:16:26,230 --> 00:16:26,240 516 00:16:26,240 --> 00:16:27,430 517 00:16:27,430 --> 00:16:28,550 518 00:16:28,550 --> 00:16:30,069 519 00:16:30,069 --> 00:16:31,990 520 00:16:31,990 --> 00:16:34,389 521 00:16:34,389 --> 00:16:35,990 522 00:16:35,990 --> 00:16:37,910 523 00:16:37,910 --> 00:16:39,269 524 00:16:39,269 --> 00:16:41,910 525 00:16:41,910 --> 00:16:41,920 526 00:16:41,920 --> 00:16:43,749 527 00:16:43,749 --> 00:16:44,949 528 00:16:44,949 --> 00:16:47,509 529 00:16:47,509 --> 00:16:48,870 530 00:16:48,870 --> 00:16:50,870 531 00:16:50,870 --> 00:16:53,990 532 00:16:53,990 --> 00:16:54,000 533 00:16:54,000 --> 00:16:54,230 534 00:16:54,230 --> 00:16:54,240 535 00:16:54,240 --> 00:16:55,749 536 00:16:55,749 --> 00:16:57,269 537 00:16:57,269 --> 00:16:59,910 538 00:16:59,910 --> 00:17:05,189 539 00:17:05,189 --> 00:17:06,949 540 00:17:06,949 --> 00:17:06,959 541 00:17:06,959 --> 00:17:07,909 542 00:17:07,909 --> 00:17:09,350 543 00:17:09,350 --> 00:17:11,990 544 00:17:11,990 --> 00:17:14,470 545 00:17:14,470 --> 00:17:14,480 546 00:17:14,480 --> 00:17:16,069 547 00:17:16,069 --> 00:17:17,350 548 00:17:17,350 --> 00:17:19,429 549 00:17:19,429 --> 00:17:21,029 550 00:17:21,029 --> 00:17:22,949 551 00:17:22,949 --> 00:17:24,230 552 00:17:24,230 --> 00:17:24,240 553 00:17:24,240 --> 00:17:26,069 554 00:17:26,069 --> 00:17:28,870 555 00:17:28,870 --> 00:17:28,880 556 00:17:28,880 --> 00:17:29,830 557 00:17:29,830 --> 00:17:31,350 558 00:17:31,350 --> 00:17:33,350 559 00:17:33,350 --> 00:17:34,870 560 00:17:34,870 --> 00:17:37,990 561 00:17:37,990 --> 00:17:40,310 562 00:17:40,310 --> 00:17:41,909 563 00:17:41,909 --> 00:17:43,990 564 00:17:43,990 --> 00:17:46,230 565 00:17:46,230 --> 00:17:48,950 566 00:17:48,950 --> 00:17:51,029 567 00:17:51,029 --> 00:17:53,029 568 00:17:53,029 --> 00:17:54,710 569 00:17:54,710 --> 00:17:54,720 570 00:17:54,720 --> 00:17:55,909 571 00:17:55,909 --> 00:17:58,070 572 00:17:58,070 --> 00:17:59,990 573 00:17:59,990 --> 00:18:01,590 574 00:18:01,590 --> 00:18:01,600 575 00:18:01,600 --> 00:18:02,870 576 00:18:02,870 --> 00:18:04,950 577 00:18:04,950 --> 00:18:07,270 578 00:18:07,270 --> 00:18:09,909 579 00:18:09,909 --> 00:18:11,909 580 00:18:11,909 --> 00:18:13,669 581 00:18:13,669 --> 00:18:15,669 582 00:18:15,669 --> 00:18:18,230 583 00:18:18,230 --> 00:18:19,750 584 00:18:19,750 --> 00:18:21,990 585 00:18:21,990 --> 00:18:24,630 586 00:18:24,630 --> 00:18:27,990 587 00:18:27,990 --> 00:18:29,830 588 00:18:29,830 --> 00:18:29,840 589 00:18:29,840 --> 00:18:30,789 590 00:18:30,789 --> 00:18:32,390 591 00:18:32,390 --> 00:18:32,400 592 00:18:32,400 --> 00:18:34,230 593 00:18:34,230 --> 00:18:35,830 594 00:18:35,830 --> 00:18:37,830 595 00:18:37,830 --> 00:18:39,830 596 00:18:39,830 --> 00:18:39,840 597 00:18:39,840 --> 00:18:40,870 598 00:18:40,870 --> 00:18:45,270 599 00:18:45,270 --> 00:18:48,310 600 00:18:48,310 --> 00:18:50,870 601 00:18:50,870 --> 00:18:54,549 602 00:18:54,549 --> 00:18:56,470 603 00:18:56,470 --> 00:19:00,150 604 00:19:00,150 --> 00:19:01,350 605 00:19:01,350 --> 00:19:03,669 606 00:19:03,669 --> 00:19:03,679 607 00:19:03,679 --> 00:19:04,470 608 00:19:04,470 --> 00:19:06,390 609 00:19:06,390 --> 00:19:09,029 610 00:19:09,029 --> 00:19:12,390 611 00:19:12,390 --> 00:19:12,400 612 00:19:12,400 --> 00:19:14,150 613 00:19:14,150 --> 00:19:17,270 614 00:19:17,270 --> 00:19:17,280 615 00:19:17,280 --> 00:19:18,230 616 00:19:18,230 --> 00:19:19,430 617 00:19:19,430 --> 00:19:21,270 618 00:19:21,270 --> 00:19:21,280 619 00:19:21,280 --> 00:19:23,350 620 00:19:23,350 --> 00:19:25,190 621 00:19:25,190 --> 00:19:27,830 622 00:19:27,830 --> 00:19:29,270 623 00:19:29,270 --> 00:19:31,909 624 00:19:31,909 --> 00:19:31,919 625 00:19:31,919 --> 00:19:32,950 626 00:19:32,950 --> 00:19:32,960 627 00:19:32,960 --> 00:19:33,830 628 00:19:33,830 --> 00:19:33,840 629 00:19:33,840 --> 00:19:34,950 630 00:19:34,950 --> 00:19:37,110 631 00:19:37,110 --> 00:19:40,230 632 00:19:40,230 --> 00:19:42,310 633 00:19:42,310 --> 00:19:43,590 634 00:19:43,590 --> 00:19:46,070 635 00:19:46,070 --> 00:19:48,710 636 00:19:48,710 --> 00:19:52,630 637 00:19:52,630 --> 00:19:54,310 638 00:19:54,310 --> 00:19:54,320 639 00:19:54,320 --> 00:19:55,510 640 00:19:55,510 --> 00:19:58,710 641 00:19:58,710 --> 00:20:00,950 642 00:20:00,950 --> 00:20:02,870 643 00:20:02,870 --> 00:20:05,909 644 00:20:05,909 --> 00:20:09,029 645 00:20:09,029 --> 00:20:09,039 646 00:20:09,039 --> 00:20:10,390 647 00:20:10,390 --> 00:20:12,070 648 00:20:12,070 --> 00:20:14,070 649 00:20:14,070 --> 00:20:15,270 650 00:20:15,270 --> 00:20:17,270 651 00:20:17,270 --> 00:20:19,909 652 00:20:19,909 --> 00:20:22,710 653 00:20:22,710 --> 00:20:22,720 654 00:20:22,720 --> 00:20:23,990 655 00:20:23,990 --> 00:20:24,000 656 00:20:24,000 --> 00:20:26,310 657 00:20:26,310 --> 00:20:27,669 658 00:20:27,669 --> 00:20:29,669 659 00:20:29,669 --> 00:20:32,830 660 00:20:32,830 --> 00:20:35,590 661 00:20:35,590 --> 00:20:37,750 662 00:20:37,750 --> 00:20:40,070 663 00:20:40,070 --> 00:20:43,270 664 00:20:43,270 --> 00:20:43,280 665 00:20:43,280 --> 00:20:44,310 666 00:20:44,310 --> 00:20:44,320 667 00:20:44,320 --> 00:20:45,510 668 00:20:45,510 --> 00:20:47,430 669 00:20:47,430 --> 00:20:49,430 670 00:20:49,430 --> 00:20:52,630 671 00:20:52,630 --> 00:20:54,789 672 00:20:54,789 --> 00:20:56,630 673 00:20:56,630 --> 00:20:58,870 674 00:20:58,870 --> 00:21:00,710 675 00:21:00,710 --> 00:21:03,029 676 00:21:03,029 --> 00:21:04,470 677 00:21:04,470 --> 00:21:06,710 678 00:21:06,710 --> 00:21:08,070 679 00:21:08,070 --> 00:21:09,669 680 00:21:09,669 --> 00:21:09,679 681 00:21:09,679 --> 00:21:10,789 682 00:21:10,789 --> 00:21:10,799 683 00:21:10,799 --> 00:21:12,149 684 00:21:12,149 --> 00:21:13,510 685 00:21:13,510 --> 00:21:15,110 686 00:21:15,110 --> 00:21:18,470 687 00:21:18,470 --> 00:21:19,750 688 00:21:19,750 --> 00:21:21,909 689 00:21:21,909 --> 00:21:23,510 690 00:21:23,510 --> 00:21:25,110 691 00:21:25,110 --> 00:21:27,350 692 00:21:27,350 --> 00:21:27,360 693 00:21:27,360 --> 00:21:30,870 694 00:21:30,870 --> 00:21:34,149 695 00:21:34,149 --> 00:21:35,669 696 00:21:35,669 --> 00:21:37,990 697 00:21:37,990 --> 00:21:39,270 698 00:21:39,270 --> 00:21:40,950 699 00:21:40,950 --> 00:21:42,830 700 00:21:42,830 --> 00:21:44,789 701 00:21:44,789 --> 00:21:44,799 702 00:21:44,799 --> 00:21:45,990 703 00:21:45,990 --> 00:21:46,000 704 00:21:46,000 --> 00:21:47,029 705 00:21:47,029 --> 00:21:48,710 706 00:21:48,710 --> 00:21:51,270 707 00:21:51,270 --> 00:21:52,870 708 00:21:52,870 --> 00:21:55,990 709 00:21:55,990 --> 00:21:58,149 710 00:21:58,149 --> 00:22:06,390 711 00:22:06,390 --> 00:22:07,830 712 00:22:07,830 --> 00:22:09,750 713 00:22:09,750 --> 00:22:12,630 714 00:22:12,630 --> 00:22:15,110 715 00:22:15,110 --> 00:22:15,120 716 00:22:15,120 --> 00:22:17,270 717 00:22:17,270 --> 00:22:19,669 718 00:22:19,669 --> 00:22:21,590 719 00:22:21,590 --> 00:22:21,600 720 00:22:21,600 --> 00:22:22,710 721 00:22:22,710 --> 00:22:22,720 722 00:22:22,720 --> 00:22:25,029 723 00:22:25,029 --> 00:22:26,710 724 00:22:26,710 --> 00:22:28,630 725 00:22:28,630 --> 00:22:30,390 726 00:22:30,390 --> 00:22:31,909 727 00:22:31,909 --> 00:22:31,919 728 00:22:31,919 --> 00:22:33,110 729 00:22:33,110 --> 00:22:35,990 730 00:22:35,990 --> 00:22:37,590 731 00:22:37,590 --> 00:22:37,600 732 00:22:37,600 --> 00:22:40,149 733 00:22:40,149 --> 00:22:42,230 734 00:22:42,230 --> 00:22:44,149 735 00:22:44,149 --> 00:22:45,669 736 00:22:45,669 --> 00:22:47,270 737 00:22:47,270 --> 00:22:49,350 738 00:22:49,350 --> 00:22:51,350 739 00:22:51,350 --> 00:22:55,270 740 00:22:55,270 --> 00:22:56,950 741 00:22:56,950 --> 00:22:58,549 742 00:22:58,549 --> 00:23:00,549 743 00:23:00,549 --> 00:23:03,270 744 00:23:03,270 --> 00:23:05,430 745 00:23:05,430 --> 00:23:05,440 746 00:23:05,440 --> 00:23:06,870 747 00:23:06,870 --> 00:23:09,190 748 00:23:09,190 --> 00:23:10,630 749 00:23:10,630 --> 00:23:12,870 750 00:23:12,870 --> 00:23:14,230 751 00:23:14,230 --> 00:23:16,950 752 00:23:16,950 --> 00:23:19,510 753 00:23:19,510 --> 00:23:19,520 754 00:23:19,520 --> 00:23:22,710 755 00:23:22,710 --> 00:23:25,029 756 00:23:25,029 --> 00:23:26,950 757 00:23:26,950 --> 00:23:28,789 758 00:23:28,789 --> 00:23:28,799 759 00:23:28,799 --> 00:23:29,750 760 00:23:29,750 --> 00:23:32,789 761 00:23:32,789 --> 00:23:34,950 762 00:23:34,950 --> 00:23:37,430 763 00:23:37,430 --> 00:23:39,510 764 00:23:39,510 --> 00:23:41,430 765 00:23:41,430 --> 00:23:41,440 766 00:23:41,440 --> 00:23:42,470 767 00:23:42,470 --> 00:23:45,110 768 00:23:45,110 --> 00:23:45,120 769 00:23:45,120 --> 00:23:46,470 770 00:23:46,470 --> 00:23:48,390 771 00:23:48,390 --> 00:23:49,830 772 00:23:49,830 --> 00:23:51,190 773 00:23:51,190 --> 00:23:53,350 774 00:23:53,350 --> 00:23:55,510 775 00:23:55,510 --> 00:23:57,590 776 00:23:57,590 --> 00:23:58,950 777 00:23:58,950 --> 00:24:00,310 778 00:24:00,310 --> 00:24:02,390 779 00:24:02,390 --> 00:24:04,870 780 00:24:04,870 --> 00:24:04,880 781 00:24:04,880 --> 00:24:05,669 782 00:24:05,669 --> 00:24:07,909 783 00:24:07,909 --> 00:24:07,919 784 00:24:07,919 --> 00:24:09,029 785 00:24:09,029 --> 00:24:11,269 786 00:24:11,269 --> 00:24:13,830 787 00:24:13,830 --> 00:24:15,510 788 00:24:15,510 --> 00:24:16,710 789 00:24:16,710 --> 00:24:16,720 790 00:24:16,720 --> 00:24:19,190 791 00:24:19,190 --> 00:24:20,310 792 00:24:20,310 --> 00:24:21,990 793 00:24:21,990 --> 00:24:24,149 794 00:24:24,149 --> 00:24:25,590 795 00:24:25,590 --> 00:24:27,669 796 00:24:27,669 --> 00:24:29,909 797 00:24:29,909 --> 00:24:31,430 798 00:24:31,430 --> 00:24:33,510 799 00:24:33,510 --> 00:24:34,870 800 00:24:34,870 --> 00:24:36,870 801 00:24:36,870 --> 00:24:36,880 802 00:24:36,880 --> 00:24:38,549 803 00:24:38,549 --> 00:24:42,549 804 00:24:42,549 --> 00:24:44,630 805 00:24:44,630 --> 00:24:47,430 806 00:24:47,430 --> 00:24:49,350 807 00:24:49,350 --> 00:24:50,870 808 00:24:50,870 --> 00:24:52,390 809 00:24:52,390 --> 00:24:53,669 810 00:24:53,669 --> 00:24:55,269 811 00:24:55,269 --> 00:24:57,830 812 00:24:57,830 --> 00:24:59,590 813 00:24:59,590 --> 00:25:01,510 814 00:25:01,510 --> 00:25:04,230 815 00:25:04,230 --> 00:25:06,149 816 00:25:06,149 --> 00:25:08,149 817 00:25:08,149 --> 00:25:10,310 818 00:25:10,310 --> 00:25:11,669 819 00:25:11,669 --> 00:25:13,350 820 00:25:13,350 --> 00:25:15,430 821 00:25:15,430 --> 00:25:18,149 822 00:25:18,149 --> 00:25:20,149 823 00:25:20,149 --> 00:25:22,310 824 00:25:22,310 --> 00:25:22,320 825 00:25:22,320 --> 00:25:24,549 826 00:25:24,549 --> 00:25:27,029 827 00:25:27,029 --> 00:25:29,669 828 00:25:29,669 --> 00:25:31,990 829 00:25:31,990 --> 00:25:34,950 830 00:25:34,950 --> 00:25:36,310 831 00:25:36,310 --> 00:25:39,029 832 00:25:39,029 --> 00:25:40,710 833 00:25:40,710 --> 00:25:43,590 834 00:25:43,590 --> 00:25:43,600 835 00:25:43,600 --> 00:25:44,630 836 00:25:44,630 --> 00:25:46,549 837 00:25:46,549 --> 00:25:48,470 838 00:25:48,470 --> 00:25:50,950 839 00:25:50,950 --> 00:25:50,960 840 00:25:50,960 --> 00:25:53,029 841 00:25:53,029 --> 00:25:55,269 842 00:25:55,269 --> 00:25:57,110 843 00:25:57,110 --> 00:25:58,710 844 00:25:58,710 --> 00:26:00,710 845 00:26:00,710 --> 00:26:03,029 846 00:26:03,029 --> 00:26:04,870 847 00:26:04,870 --> 00:26:07,750 848 00:26:07,750 --> 00:26:07,760 849 00:26:07,760 --> 00:26:10,630 850 00:26:10,630 --> 00:26:11,909 851 00:26:11,909 --> 00:26:13,350 852 00:26:13,350 --> 00:26:15,029 853 00:26:15,029 --> 00:26:16,710 854 00:26:16,710 --> 00:26:17,830 855 00:26:17,830 --> 00:26:20,710 856 00:26:20,710 --> 00:26:22,470 857 00:26:22,470 --> 00:26:23,590 858 00:26:23,590 --> 00:26:23,600 859 00:26:23,600 --> 00:26:25,110 860 00:26:25,110 --> 00:26:26,870 861 00:26:26,870 --> 00:26:26,880 862 00:26:26,880 --> 00:26:27,990 863 00:26:27,990 --> 00:26:29,750 864 00:26:29,750 --> 00:26:29,760 865 00:26:29,760 --> 00:26:31,190 866 00:26:31,190 --> 00:26:33,029 867 00:26:33,029 --> 00:26:34,470 868 00:26:34,470 --> 00:26:34,480 869 00:26:34,480 --> 00:26:35,990 870 00:26:35,990 --> 00:26:38,870 871 00:26:38,870 --> 00:26:40,310 872 00:26:40,310 --> 00:26:43,190 873 00:26:43,190 --> 00:26:44,789 874 00:26:44,789 --> 00:26:46,310 875 00:26:46,310 --> 00:26:47,350 876 00:26:47,350 --> 00:26:49,110 877 00:26:49,110 --> 00:26:51,110 878 00:26:51,110 --> 00:26:52,630 879 00:26:52,630 --> 00:26:52,640 880 00:26:52,640 --> 00:26:56,950 881 00:26:56,950 --> 00:27:00,310 882 00:27:00,310 --> 00:27:02,390 883 00:27:02,390 --> 00:27:04,549 884 00:27:04,549 --> 00:27:07,510 885 00:27:07,510 --> 00:27:07,520 886 00:27:07,520 --> 00:27:08,710 887 00:27:08,710 --> 00:27:10,390 888 00:27:10,390 --> 00:27:13,029 889 00:27:13,029 --> 00:27:14,870 890 00:27:14,870 --> 00:27:16,390 891 00:27:16,390 --> 00:27:17,830 892 00:27:17,830 --> 00:27:19,269 893 00:27:19,269 --> 00:27:20,630 894 00:27:20,630 --> 00:27:23,510 895 00:27:23,510 --> 00:27:25,750 896 00:27:25,750 --> 00:27:27,590 897 00:27:27,590 --> 00:27:32,630 898 00:27:32,630 --> 00:27:34,070 899 00:27:34,070 --> 00:27:35,669 900 00:27:35,669 --> 00:27:37,750 901 00:27:37,750 --> 00:27:39,830 902 00:27:39,830 --> 00:27:41,909 903 00:27:41,909 --> 00:27:45,669 904 00:27:45,669 --> 00:27:45,679 905 00:27:45,679 --> 00:27:46,870 906 00:27:46,870 --> 00:27:48,710 907 00:27:48,710 --> 00:27:51,269 908 00:27:51,269 --> 00:27:53,909 909 00:27:53,909 --> 00:27:55,750 910 00:27:55,750 --> 00:27:57,110 911 00:27:57,110 --> 00:27:59,029 912 00:27:59,029 --> 00:28:00,830 913 00:28:00,830 --> 00:28:00,840 914 00:28:00,840 --> 00:28:02,470 915 00:28:02,470 --> 00:28:03,750 916 00:28:03,750 --> 00:28:06,149 917 00:28:06,149 --> 00:28:08,710 918 00:28:08,710 --> 00:28:10,630 919 00:28:10,630 --> 00:28:12,149 920 00:28:12,149 --> 00:28:14,230 921 00:28:14,230 --> 00:28:16,549 922 00:28:16,549 --> 00:28:19,669 923 00:28:19,669 --> 00:28:19,679 924 00:28:19,679 --> 00:28:20,710 925 00:28:20,710 --> 00:28:20,720 926 00:28:20,720 --> 00:28:21,750 927 00:28:21,750 --> 00:28:23,909 928 00:28:23,909 --> 00:28:25,909 929 00:28:25,909 --> 00:28:25,919 930 00:28:25,919 --> 00:28:27,190 931 00:28:27,190 --> 00:28:28,950 932 00:28:28,950 --> 00:28:31,110 933 00:28:31,110 --> 00:28:33,110 934 00:28:33,110 --> 00:28:34,870 935 00:28:34,870 --> 00:28:38,149 936 00:28:38,149 --> 00:28:39,990 937 00:28:39,990 --> 00:28:42,710 938 00:28:42,710 --> 00:28:45,830 939 00:28:45,830 --> 00:28:47,269 940 00:28:47,269 --> 00:28:48,630 941 00:28:48,630 --> 00:28:51,510 942 00:28:51,510 --> 00:28:51,520 943 00:28:51,520 --> 00:28:52,710 944 00:28:52,710 --> 00:28:54,870 945 00:28:54,870 --> 00:28:56,149 946 00:28:56,149 --> 00:28:58,710 947 00:28:58,710 --> 00:28:58,720 948 00:28:58,720 --> 00:29:01,430 949 00:29:01,430 --> 00:29:04,230 950 00:29:04,230 --> 00:29:04,240 951 00:29:04,240 --> 00:29:06,710 952 00:29:06,710 --> 00:29:08,789 953 00:29:08,789 --> 00:29:10,070 954 00:29:10,070 --> 00:29:13,430 955 00:29:13,430 --> 00:29:17,029 956 00:29:17,029 --> 00:29:17,039 957 00:29:17,039 --> 00:29:18,950 958 00:29:18,950 --> 00:29:20,310 959 00:29:20,310 --> 00:29:22,149 960 00:29:22,149 --> 00:29:23,990 961 00:29:23,990 --> 00:29:26,149 962 00:29:26,149 --> 00:29:28,710 963 00:29:28,710 --> 00:29:30,710 964 00:29:30,710 --> 00:29:32,789 965 00:29:32,789 --> 00:29:34,710 966 00:29:34,710 --> 00:29:34,720 967 00:29:34,720 --> 00:29:35,750 968 00:29:35,750 --> 00:29:37,590 969 00:29:37,590 --> 00:29:41,029 970 00:29:41,029 --> 00:29:43,590 971 00:29:43,590 --> 00:29:43,600 972 00:29:43,600 --> 00:29:44,389 973 00:29:44,389 --> 00:29:46,389 974 00:29:46,389 --> 00:29:48,549 975 00:29:48,549 --> 00:29:48,559 976 00:29:48,559 --> 00:29:49,590 977 00:29:49,590 --> 00:29:51,110 978 00:29:51,110 --> 00:29:51,120 979 00:29:51,120 --> 00:29:53,190 980 00:29:53,190 --> 00:29:56,549 981 00:29:56,549 --> 00:30:01,190 982 00:30:01,190 --> 00:30:03,430 983 00:30:03,430 --> 00:30:03,440 984 00:30:03,440 --> 00:30:04,789 985 00:30:04,789 --> 00:30:07,029 986 00:30:07,029 --> 00:30:09,430 987 00:30:09,430 --> 00:30:10,789 988 00:30:10,789 --> 00:30:13,269 989 00:30:13,269 --> 00:30:13,279 990 00:30:13,279 --> 00:30:15,110 991 00:30:15,110 --> 00:30:16,789 992 00:30:16,789 --> 00:30:18,630 993 00:30:18,630 --> 00:30:20,549 994 00:30:20,549 --> 00:30:22,630 995 00:30:22,630 --> 00:30:24,230 996 00:30:24,230 --> 00:30:26,149 997 00:30:26,149 --> 00:30:28,230 998 00:30:28,230 --> 00:30:30,230 999 00:30:30,230 --> 00:30:32,549 1000 00:30:32,549 --> 00:30:35,669 1001 00:30:35,669 --> 00:30:37,830 1002 00:30:37,830 --> 00:30:41,990 1003 00:30:41,990 --> 00:30:42,000 1004 00:30:42,000 --> 00:30:43,750 1005 00:30:43,750 --> 00:30:43,760 1006 00:30:43,760 --> 00:30:44,630 1007 00:30:44,630 --> 00:30:44,640 1008 00:30:44,640 --> 00:30:45,909 1009 00:30:45,909 --> 00:30:45,919 1010 00:30:45,919 --> 00:30:46,870 1011 00:30:46,870 --> 00:30:48,389 1012 00:30:48,389 --> 00:30:50,230 1013 00:30:50,230 --> 00:30:51,990 1014 00:30:51,990 --> 00:30:53,909 1015 00:30:53,909 --> 00:30:53,919 1016 00:30:53,919 --> 00:30:55,269 1017 00:30:55,269 --> 00:30:58,070 1018 00:30:58,070 --> 00:31:00,230 1019 00:31:00,230 --> 00:31:02,549 1020 00:31:02,549 --> 00:31:05,350 1021 00:31:05,350 --> 00:31:06,630 1022 00:31:06,630 --> 00:31:10,950 1023 00:31:10,950 --> 00:31:13,350 1024 00:31:13,350 --> 00:31:15,110 1025 00:31:15,110 --> 00:31:17,669 1026 00:31:17,669 --> 00:31:19,830 1027 00:31:19,830 --> 00:31:21,750 1028 00:31:21,750 --> 00:31:23,990 1029 00:31:23,990 --> 00:31:25,830 1030 00:31:25,830 --> 00:31:27,269 1031 00:31:27,269 --> 00:31:29,029 1032 00:31:29,029 --> 00:31:30,950 1033 00:31:30,950 --> 00:31:33,430 1034 00:31:33,430 --> 00:31:35,430 1035 00:31:35,430 --> 00:31:37,990 1036 00:31:37,990 --> 00:31:40,389 1037 00:31:40,389 --> 00:31:42,310 1038 00:31:42,310 --> 00:31:45,909 1039 00:31:45,909 --> 00:31:47,430 1040 00:31:47,430 --> 00:31:49,909 1041 00:31:49,909 --> 00:31:52,470 1042 00:31:52,470 --> 00:31:58,149 1043 00:31:58,149 --> 00:32:01,190 1044 00:32:01,190 --> 00:32:02,710 1045 00:32:02,710 --> 00:32:04,870 1046 00:32:04,870 --> 00:32:07,350 1047 00:32:07,350 --> 00:32:10,149 1048 00:32:10,149 --> 00:32:10,159 1049 00:32:10,159 --> 00:32:12,830 1050 00:32:12,830 --> 00:32:12,840 1051 00:32:12,840 --> 00:32:14,630 1052 00:32:14,630 --> 00:32:17,029 1053 00:32:17,029 --> 00:32:19,509 1054 00:32:19,509 --> 00:32:20,950 1055 00:32:20,950 --> 00:32:22,950 1056 00:32:22,950 --> 00:32:26,070 1057 00:32:26,070 --> 00:32:28,310 1058 00:32:28,310 --> 00:32:28,320 1059 00:32:28,320 --> 00:32:31,430 1060 00:32:31,430 --> 00:32:33,909 1061 00:32:33,909 --> 00:32:35,750 1062 00:32:35,750 --> 00:32:37,750 1063 00:32:37,750 --> 00:32:41,190 1064 00:32:41,190 --> 00:32:43,509 1065 00:32:43,509 --> 00:32:45,269 1066 00:32:45,269 --> 00:32:47,509 1067 00:32:47,509 --> 00:32:49,029 1068 00:32:49,029 --> 00:32:51,750 1069 00:32:51,750 --> 00:32:53,350 1070 00:32:53,350 --> 00:32:56,230 1071 00:32:56,230 --> 00:32:57,830 1072 00:32:57,830 --> 00:32:59,430 1073 00:32:59,430 --> 00:33:00,870 1074 00:33:00,870 --> 00:33:02,230 1075 00:33:02,230 --> 00:33:03,750 1076 00:33:03,750 --> 00:33:05,430 1077 00:33:05,430 --> 00:33:06,710 1078 00:33:06,710 --> 00:33:09,110 1079 00:33:09,110 --> 00:33:10,389 1080 00:33:10,389 --> 00:33:12,230 1081 00:33:12,230 --> 00:33:14,070 1082 00:33:14,070 --> 00:33:15,830 1083 00:33:15,830 --> 00:33:20,149 1084 00:33:20,149 --> 00:33:20,159 1085 00:33:20,159 --> 00:33:21,750 1086 00:33:21,750 --> 00:33:23,830 1087 00:33:23,830 --> 00:33:26,230 1088 00:33:26,230 --> 00:33:26,240 1089 00:33:26,240 --> 00:33:27,110 1090 00:33:27,110 --> 00:33:31,990 1091 00:33:31,990 --> 00:33:33,430 1092 00:33:33,430 --> 00:33:35,430 1093 00:33:35,430 --> 00:33:38,470 1094 00:33:38,470 --> 00:33:44,070 1095 00:33:44,070 --> 00:33:44,080 1096 00:33:44,080 --> 00:33:45,509 1097 00:33:45,509 --> 00:33:45,519 1098 00:33:45,519 --> 00:33:46,950 1099 00:33:46,950 --> 00:33:49,269 1100 00:33:49,269 --> 00:33:49,279 1101 00:33:49,279 --> 00:33:50,549 1102 00:33:50,549 --> 00:33:52,549 1103 00:33:52,549 --> 00:33:54,870 1104 00:33:54,870 --> 00:33:57,110 1105 00:33:57,110 --> 00:33:59,430 1106 00:33:59,430 --> 00:34:01,350 1107 00:34:01,350 --> 00:34:04,549 1108 00:34:04,549 --> 00:34:06,149 1109 00:34:06,149 --> 00:34:08,389 1110 00:34:08,389 --> 00:34:11,909 1111 00:34:11,909 --> 00:34:13,829 1112 00:34:13,829 --> 00:34:15,589 1113 00:34:15,589 --> 00:34:15,599 1114 00:34:15,599 --> 00:34:17,829 1115 00:34:17,829 --> 00:34:17,839 1116 00:34:17,839 --> 00:34:19,510 1117 00:34:19,510 --> 00:34:19,520 1118 00:34:19,520 --> 00:34:23,190 1119 00:34:23,190 --> 00:34:26,069 1120 00:34:26,069 --> 00:34:28,950 1121 00:34:28,950 --> 00:34:30,790 1122 00:34:30,790 --> 00:34:30,800 1123 00:34:30,800 --> 00:34:32,389 1124 00:34:32,389 --> 00:34:34,869 1125 00:34:34,869 --> 00:34:36,869 1126 00:34:36,869 --> 00:34:41,349 1127 00:34:41,349 --> 00:34:42,950 1128 00:34:42,950 --> 00:34:44,950 1129 00:34:44,950 --> 00:34:46,310 1130 00:34:46,310 --> 00:34:48,149 1131 00:34:48,149 --> 00:34:49,510 1132 00:34:49,510 --> 00:34:53,589 1133 00:34:53,589 --> 00:34:55,589 1134 00:34:55,589 --> 00:34:55,599 1135 00:34:55,599 --> 00:34:57,589 1136 00:34:57,589 --> 00:34:59,270 1137 00:34:59,270 --> 00:35:01,109 1138 00:35:01,109 --> 00:35:03,349 1139 00:35:03,349 --> 00:35:06,710 1140 00:35:06,710 --> 00:35:10,390 1141 00:35:10,390 --> 00:35:13,510 1142 00:35:13,510 --> 00:35:15,990 1143 00:35:15,990 --> 00:35:18,870 1144 00:35:18,870 --> 00:35:20,870 1145 00:35:20,870 --> 00:35:23,510 1146 00:35:23,510 --> 00:35:25,670 1147 00:35:25,670 --> 00:35:28,069 1148 00:35:28,069 --> 00:35:30,630 1149 00:35:30,630 --> 00:35:32,390 1150 00:35:32,390 --> 00:35:32,400 1151 00:35:32,400 --> 00:35:33,510 1152 00:35:33,510 --> 00:35:33,520 1153 00:35:33,520 --> 00:35:34,790 1154 00:35:34,790 --> 00:35:36,630 1155 00:35:36,630 --> 00:35:41,270 1156 00:35:41,270 --> 00:35:43,750 1157 00:35:43,750 --> 00:35:46,550 1158 00:35:46,550 --> 00:35:48,950 1159 00:35:48,950 --> 00:35:48,960 1160 00:35:48,960 --> 00:35:50,550 1161 00:35:50,550 --> 00:35:53,190 1162 00:35:53,190 --> 00:35:55,030 1163 00:35:55,030 --> 00:35:57,190 1164 00:35:57,190 --> 00:35:59,910 1165 00:35:59,910 --> 00:35:59,920 1166 00:35:59,920 --> 00:36:01,030 1167 00:36:01,030 --> 00:36:04,310 1168 00:36:04,310 --> 00:36:04,320 1169 00:36:04,320 --> 00:36:08,710 1170 00:36:08,710 --> 00:36:10,390 1171 00:36:10,390 --> 00:36:12,390 1172 00:36:12,390 --> 00:36:14,710 1173 00:36:14,710 --> 00:36:14,720 1174 00:36:14,720 --> 00:36:15,589 1175 00:36:15,589 --> 00:36:17,030 1176 00:36:17,030 --> 00:36:20,630 1177 00:36:20,630 --> 00:36:22,710 1178 00:36:22,710 --> 00:36:24,710 1179 00:36:24,710 --> 00:36:27,990 1180 00:36:27,990 --> 00:36:30,710 1181 00:36:30,710 --> 00:36:30,720 1182 00:36:30,720 --> 00:36:31,829 1183 00:36:31,829 --> 00:36:33,829 1184 00:36:33,829 --> 00:36:36,550 1185 00:36:36,550 --> 00:36:39,750 1186 00:36:39,750 --> 00:36:42,550 1187 00:36:42,550 --> 00:36:45,510 1188 00:36:45,510 --> 00:36:47,349 1189 00:36:47,349 --> 00:36:49,349 1190 00:36:49,349 --> 00:36:51,349 1191 00:36:51,349 --> 00:36:53,510 1192 00:36:53,510 --> 00:36:56,069 1193 00:36:56,069 --> 00:36:59,109 1194 00:36:59,109 --> 00:37:01,510 1195 00:37:01,510 --> 00:37:03,270 1196 00:37:03,270 --> 00:37:06,870 1197 00:37:06,870 --> 00:37:08,390 1198 00:37:08,390 --> 00:37:09,910 1199 00:37:09,910 --> 00:37:13,589 1200 00:37:13,589 --> 00:37:17,589 1201 00:37:17,589 --> 00:37:19,750 1202 00:37:19,750 --> 00:37:21,430 1203 00:37:21,430 --> 00:37:24,870 1204 00:37:24,870 --> 00:37:27,430 1205 00:37:27,430 --> 00:37:29,990 1206 00:37:29,990 --> 00:37:32,630 1207 00:37:32,630 --> 00:37:35,109 1208 00:37:35,109 --> 00:37:36,950 1209 00:37:36,950 --> 00:37:40,630 1210 00:37:40,630 --> 00:37:42,310 1211 00:37:42,310 --> 00:37:42,320 1212 00:37:42,320 --> 00:37:43,750 1213 00:37:43,750 --> 00:37:47,030 1214 00:37:47,030 --> 00:37:48,710 1215 00:37:48,710 --> 00:37:50,630 1216 00:37:50,630 --> 00:37:52,069 1217 00:37:52,069 --> 00:37:54,390 1218 00:37:54,390 --> 00:37:56,069 1219 00:37:56,069 --> 00:37:56,079 1220 00:37:56,079 --> 00:37:58,470 1221 00:37:58,470 --> 00:38:01,109 1222 00:38:01,109 --> 00:38:03,589 1223 00:38:03,589 --> 00:38:05,270 1224 00:38:05,270 --> 00:38:08,710 1225 00:38:08,710 --> 00:38:08,720 1226 00:38:08,720 --> 00:38:10,630 1227 00:38:10,630 --> 00:38:12,950 1228 00:38:12,950 --> 00:38:14,790 1229 00:38:14,790 --> 00:38:18,950 1230 00:38:18,950 --> 00:38:21,190 1231 00:38:21,190 --> 00:38:22,710 1232 00:38:22,710 --> 00:38:27,109 1233 00:38:27,109 --> 00:38:29,270 1234 00:38:29,270 --> 00:38:36,550 1235 00:38:36,550 --> 00:38:38,630 1236 00:38:38,630 --> 00:38:42,710 1237 00:38:42,710 --> 00:38:45,030 1238 00:38:45,030 --> 00:38:49,190 1239 00:38:49,190 --> 00:38:49,200 1240 00:38:49,200 --> 00:38:50,390 1241 00:38:50,390 --> 00:38:52,950 1242 00:38:52,950 --> 00:38:53,990 1243 00:38:53,990 --> 00:38:57,349 1244 00:38:57,349 --> 00:39:01,510 1245 00:39:01,510 --> 00:39:03,510 1246 00:39:03,510 --> 00:39:05,589 1247 00:39:05,589 --> 00:39:05,599 1248 00:39:05,599 --> 00:39:06,550 1249 00:39:06,550 --> 00:39:08,390 1250 00:39:08,390 --> 00:39:10,790 1251 00:39:10,790 --> 00:39:11,990 1252 00:39:11,990 --> 00:39:15,270 1253 00:39:15,270 --> 00:39:17,589 1254 00:39:17,589 --> 00:39:20,310 1255 00:39:20,310 --> 00:39:22,870 1256 00:39:22,870 --> 00:39:24,470 1257 00:39:24,470 --> 00:39:24,480 1258 00:39:24,480 --> 00:39:25,510 1259 00:39:25,510 --> 00:39:27,750 1260 00:39:27,750 --> 00:39:27,760 1261 00:39:27,760 --> 00:39:29,270 1262 00:39:29,270 --> 00:39:31,109 1263 00:39:31,109 --> 00:39:32,710 1264 00:39:32,710 --> 00:39:35,030 1265 00:39:35,030 --> 00:39:36,390 1266 00:39:36,390 --> 00:39:41,190 1267 00:39:41,190 --> 00:39:41,200 1268 00:39:41,200 --> 00:39:42,550 1269 00:39:42,550 --> 00:39:44,630 1270 00:39:44,630 --> 00:39:48,790 1271 00:39:48,790 --> 00:39:48,800 1272 00:39:48,800 --> 00:39:49,910 1273 00:39:49,910 --> 00:39:51,910 1274 00:39:51,910 --> 00:39:51,920 1275 00:39:51,920 --> 00:39:54,790 1276 00:39:54,790 --> 00:39:57,670 1277 00:39:57,670 --> 00:39:59,190 1278 00:39:59,190 --> 00:39:59,200 1279 00:39:59,200 --> 00:40:00,310 1280 00:40:00,310 --> 00:40:02,150 1281 00:40:02,150 --> 00:40:05,190 1282 00:40:05,190 --> 00:40:07,270 1283 00:40:07,270 --> 00:40:08,950 1284 00:40:08,950 --> 00:40:10,390 1285 00:40:10,390 --> 00:40:14,069 1286 00:40:14,069 --> 00:40:15,910 1287 00:40:15,910 --> 00:40:18,550 1288 00:40:18,550 --> 00:40:20,550 1289 00:40:20,550 --> 00:40:20,560 1290 00:40:20,560 --> 00:40:21,910 1291 00:40:21,910 --> 00:40:24,550 1292 00:40:24,550 --> 00:40:29,270 1293 00:40:29,270 --> 00:40:32,470 1294 00:40:32,470 --> 00:40:35,430 1295 00:40:35,430 --> 00:40:37,990 1296 00:40:37,990 --> 00:40:39,990 1297 00:40:39,990 --> 00:40:41,829 1298 00:40:41,829 --> 00:40:43,990 1299 00:40:43,990 --> 00:40:45,670 1300 00:40:45,670 --> 00:40:45,680 1301 00:40:45,680 --> 00:40:46,870 1302 00:40:46,870 --> 00:40:46,880 1303 00:40:46,880 --> 00:40:48,550 1304 00:40:48,550 --> 00:40:50,150 1305 00:40:50,150 --> 00:40:52,470 1306 00:40:52,470 --> 00:40:55,589 1307 00:40:55,589 --> 00:40:57,589 1308 00:40:57,589 --> 00:41:00,150 1309 00:41:00,150 --> 00:41:02,710 1310 00:41:02,710 --> 00:41:04,790 1311 00:41:04,790 --> 00:41:07,109 1312 00:41:07,109 --> 00:41:08,230 1313 00:41:08,230 --> 00:41:09,349 1314 00:41:09,349 --> 00:41:09,359 1315 00:41:09,359 --> 00:41:11,510 1316 00:41:11,510 --> 00:41:12,870 1317 00:41:12,870 --> 00:41:15,030 1318 00:41:15,030 --> 00:41:18,150 1319 00:41:18,150 --> 00:41:20,150 1320 00:41:20,150 --> 00:41:20,160 1321 00:41:20,160 --> 00:41:21,510 1322 00:41:21,510 --> 00:41:24,950 1323 00:41:24,950 --> 00:41:26,390 1324 00:41:26,390 --> 00:41:28,309 1325 00:41:28,309 --> 00:41:29,750 1326 00:41:29,750 --> 00:41:31,990 1327 00:41:31,990 --> 00:41:33,270 1328 00:41:33,270 --> 00:41:36,069 1329 00:41:36,069 --> 00:41:38,790 1330 00:41:38,790 --> 00:41:38,800 1331 00:41:38,800 --> 00:41:40,870 1332 00:41:40,870 --> 00:41:40,880 1333 00:41:40,880 --> 00:41:41,910 1334 00:41:41,910 --> 00:41:41,920 1335 00:41:41,920 --> 00:41:43,510 1336 00:41:43,510 --> 00:41:45,030 1337 00:41:45,030 --> 00:41:47,589 1338 00:41:47,589 --> 00:41:49,270 1339 00:41:49,270 --> 00:41:51,670 1340 00:41:51,670 --> 00:41:53,510 1341 00:41:53,510 --> 00:41:55,750 1342 00:41:55,750 --> 00:41:55,760 1343 00:41:55,760 --> 00:41:57,109 1344 00:41:57,109 --> 00:41:58,710 1345 00:41:58,710 --> 00:42:00,829 1346 00:42:00,829 --> 00:42:00,839 1347 00:42:00,839 --> 00:42:02,790 1348 00:42:02,790 --> 00:42:04,309 1349 00:42:04,309 --> 00:42:06,550 1350 00:42:06,550 --> 00:42:08,150 1351 00:42:08,150 --> 00:42:09,349 1352 00:42:09,349 --> 00:42:11,430 1353 00:42:11,430 --> 00:42:13,109 1354 00:42:13,109 --> 00:42:15,589 1355 00:42:15,589 --> 00:42:18,150 1356 00:42:18,150 --> 00:42:19,750 1357 00:42:19,750 --> 00:42:19,760 1358 00:42:19,760 --> 00:42:20,870 1359 00:42:20,870 --> 00:42:23,190 1360 00:42:23,190 --> 00:42:26,390 1361 00:42:26,390 --> 00:42:28,150 1362 00:42:28,150 --> 00:42:29,750 1363 00:42:29,750 --> 00:42:30,790 1364 00:42:30,790 --> 00:42:31,910 1365 00:42:31,910 --> 00:42:33,430 1366 00:42:33,430 --> 00:42:33,440 1367 00:42:33,440 --> 00:42:36,230 1368 00:42:36,230 --> 00:42:38,470 1369 00:42:38,470 --> 00:42:38,480 1370 00:42:38,480 --> 00:42:41,750 1371 00:42:41,750 --> 00:42:43,430 1372 00:42:43,430 --> 00:42:47,990 1373 00:42:47,990 --> 00:42:48,000 1374 00:42:48,000 --> 00:42:48,290 1375 00:42:48,290 --> 00:42:48,300 1376 00:42:48,300 --> 00:42:51,430 1377 00:42:51,430 --> 00:42:51,440 1378 00:42:51,440 --> 00:42:52,950 1379 00:42:52,950 --> 00:42:52,960 1380 00:42:52,960 --> 00:43:01,030 1381 00:43:01,030 --> 00:43:03,829 1382 00:43:03,829 --> 00:43:03,839 1383 00:43:03,839 --> 00:43:07,829 1384 00:43:07,829 --> 00:43:11,670 1385 00:43:11,670 --> 00:43:13,910 1386 00:43:13,910 --> 00:43:15,990 1387 00:43:15,990 --> 00:43:18,710 1388 00:43:18,710 --> 00:43:22,150 1389 00:43:22,150 --> 00:43:22,160 1390 00:43:22,160 --> 00:43:23,030 1391 00:43:23,030 --> 00:43:25,270 1392 00:43:25,270 --> 00:43:27,270 1393 00:43:27,270 --> 00:43:27,280 1394 00:43:27,280 --> 00:43:29,030 1395 00:43:29,030 --> 00:43:32,230 1396 00:43:32,230 --> 00:43:35,589 1397 00:43:35,589 --> 00:43:37,349 1398 00:43:37,349 --> 00:43:39,030 1399 00:43:39,030 --> 00:43:41,349 1400 00:43:41,349 --> 00:43:43,349 1401 00:43:43,349 --> 00:43:43,359 1402 00:43:43,359 --> 00:43:43,720 1403 00:43:43,720 --> 00:43:43,730 1404 00:43:43,730 --> 00:43:45,430 1405 00:43:45,430 --> 00:43:47,430 1406 00:43:47,430 --> 00:43:49,030 1407 00:43:49,030 --> 00:43:50,710 1408 00:43:50,710 --> 00:43:52,790 1409 00:43:52,790 --> 00:43:55,750 1410 00:43:55,750 --> 00:43:58,069 1411 00:43:58,069 --> 00:44:00,069 1412 00:44:00,069 --> 00:44:01,910 1413 00:44:01,910 --> 00:44:04,390 1414 00:44:04,390 --> 00:44:06,069 1415 00:44:06,069 --> 00:44:07,349 1416 00:44:07,349 --> 00:44:09,910 1417 00:44:09,910 --> 00:44:09,920 1418 00:44:09,920 --> 00:44:10,950 1419 00:44:10,950 --> 00:44:13,829 1420 00:44:13,829 --> 00:44:15,670 1421 00:44:15,670 --> 00:44:18,390 1422 00:44:18,390 --> 00:44:19,990 1423 00:44:19,990 --> 00:44:22,550 1424 00:44:22,550 --> 00:44:24,550 1425 00:44:24,550 --> 00:44:24,560 1426 00:44:24,560 --> 00:44:25,270 1427 00:44:25,270 --> 00:44:27,030 1428 00:44:27,030 --> 00:44:31,109 1429 00:44:31,109 --> 00:44:34,150 1430 00:44:34,150 --> 00:44:34,160 1431 00:44:34,160 --> 00:44:35,349 1432 00:44:35,349 --> 00:44:38,069 1433 00:44:38,069 --> 00:44:39,750 1434 00:44:39,750 --> 00:44:42,550 1435 00:44:42,550 --> 00:44:44,790 1436 00:44:44,790 --> 00:44:47,510 1437 00:44:47,510 --> 00:44:49,190 1438 00:44:49,190 --> 00:44:51,349 1439 00:44:51,349 --> 00:44:53,190 1440 00:44:53,190 --> 00:44:54,870 1441 00:44:54,870 --> 00:44:56,150 1442 00:44:56,150 --> 00:44:59,430 1443 00:44:59,430 --> 00:45:02,630 1444 00:45:02,630 --> 00:45:04,550 1445 00:45:04,550 --> 00:45:06,150 1446 00:45:06,150 --> 00:45:07,670 1447 00:45:07,670 --> 00:45:09,829 1448 00:45:09,829 --> 00:45:12,230 1449 00:45:12,230 --> 00:45:14,950 1450 00:45:14,950 --> 00:45:16,150 1451 00:45:16,150 --> 00:45:19,349 1452 00:45:19,349 --> 00:45:19,359 1453 00:45:19,359 --> 00:45:19,720 1454 00:45:19,720 --> 00:45:19,730 1455 00:45:19,730 --> 00:45:22,309 1456 00:45:22,309 --> 00:45:24,550 1457 00:45:24,550 --> 00:45:26,309 1458 00:45:26,309 --> 00:45:29,349 1459 00:45:29,349 --> 00:45:32,230 1460 00:45:32,230 --> 00:45:32,240 1461 00:45:32,240 --> 00:45:33,589 1462 00:45:33,589 --> 00:45:35,190 1463 00:45:35,190 --> 00:45:37,349 1464 00:45:37,349 --> 00:45:37,359 1465 00:45:37,359 --> 00:45:38,550 1466 00:45:38,550 --> 00:45:41,270 1467 00:45:41,270 --> 00:45:43,589 1468 00:45:43,589 --> 00:45:46,390 1469 00:45:46,390 --> 00:45:48,390 1470 00:45:48,390 --> 00:45:50,390 1471 00:45:50,390 --> 00:45:51,430 1472 00:45:51,430 --> 00:45:53,349 1473 00:45:53,349 --> 00:45:56,950 1474 00:45:56,950 --> 00:45:59,510 1475 00:45:59,510 --> 00:46:01,750 1476 00:46:01,750 --> 00:46:04,470 1477 00:46:04,470 --> 00:46:07,109 1478 00:46:07,109 --> 00:46:08,550 1479 00:46:08,550 --> 00:46:13,829 1480 00:46:13,829 --> 00:46:15,990 1481 00:46:15,990 --> 00:46:17,910 1482 00:46:17,910 --> 00:46:19,990 1483 00:46:19,990 --> 00:46:22,710 1484 00:46:22,710 --> 00:46:24,790 1485 00:46:24,790 --> 00:46:26,550 1486 00:46:26,550 --> 00:46:26,560 1487 00:46:26,560 --> 00:46:28,390 1488 00:46:28,390 --> 00:46:28,400 1489 00:46:28,400 --> 00:46:33,589 1490 00:46:33,589 --> 00:46:36,470 1491 00:46:36,470 --> 00:46:38,150 1492 00:46:38,150 --> 00:46:38,160 1493 00:46:38,160 --> 00:46:39,190 1494 00:46:39,190 --> 00:46:42,470 1495 00:46:42,470 --> 00:46:42,480 1496 00:46:42,480 --> 00:46:44,230 1497 00:46:44,230 --> 00:46:46,230 1498 00:46:46,230 --> 00:46:48,150 1499 00:46:48,150 --> 00:46:50,470 1500 00:46:50,470 --> 00:46:52,630 1501 00:46:52,630 --> 00:46:54,950 1502 00:46:54,950 --> 00:46:58,710 1503 00:46:58,710 --> 00:46:58,720 1504 00:46:58,720 --> 00:47:00,390 1505 00:47:00,390 --> 00:47:01,829 1506 00:47:01,829 --> 00:47:03,109 1507 00:47:03,109 --> 00:47:04,550 1508 00:47:04,550 --> 00:47:06,710 1509 00:47:06,710 --> 00:47:11,190 1510 00:47:11,190 --> 00:47:11,200 1511 00:47:11,200 --> 00:47:12,630 1512 00:47:12,630 --> 00:47:14,870 1513 00:47:14,870 --> 00:47:16,230 1514 00:47:16,230 --> 00:47:18,150 1515 00:47:18,150 --> 00:47:21,109 1516 00:47:21,109 --> 00:47:23,829 1517 00:47:23,829 --> 00:47:23,839 1518 00:47:23,839 --> 00:47:24,950 1519 00:47:24,950 --> 00:47:24,960 1520 00:47:24,960 --> 00:47:27,910 1521 00:47:27,910 --> 00:47:30,950 1522 00:47:30,950 --> 00:47:33,430 1523 00:47:33,430 --> 00:47:37,349 1524 00:47:37,349 --> 00:47:40,150 1525 00:47:40,150 --> 00:47:40,160 1526 00:47:40,160 --> 00:47:42,230 1527 00:47:42,230 --> 00:47:42,240 1528 00:47:42,240 --> 00:47:43,430 1529 00:47:43,430 --> 00:47:44,870 1530 00:47:44,870 --> 00:47:46,870 1531 00:47:46,870 --> 00:47:46,880 1532 00:47:46,880 --> 00:47:47,829 1533 00:47:47,829 --> 00:47:50,230 1534 00:47:50,230 --> 00:47:54,069 1535 00:47:54,069 --> 00:47:54,079 1536 00:47:54,079 --> 00:47:55,829 1537 00:47:55,829 --> 00:47:55,839 1538 00:47:55,839 --> 00:47:57,750 1539 00:47:57,750 --> 00:47:59,990 1540 00:47:59,990 --> 00:48:02,069 1541 00:48:02,069 --> 00:48:02,079 1542 00:48:02,079 --> 00:48:03,589 1543 00:48:03,589 --> 00:48:06,549 1544 00:48:06,549 --> 00:48:08,230 1545 00:48:08,230 --> 00:48:10,870 1546 00:48:10,870 --> 00:48:12,150 1547 00:48:12,150 --> 00:48:14,870 1548 00:48:14,870 --> 00:48:16,549 1549 00:48:16,549 --> 00:48:18,630 1550 00:48:18,630 --> 00:48:21,109 1551 00:48:21,109 --> 00:48:22,710 1552 00:48:22,710 --> 00:48:24,230 1553 00:48:24,230 --> 00:48:25,990 1554 00:48:25,990 --> 00:48:28,309 1555 00:48:28,309 --> 00:48:29,829 1556 00:48:29,829 --> 00:48:31,589 1557 00:48:31,589 --> 00:48:31,599 1558 00:48:31,599 --> 00:48:32,549 1559 00:48:32,549 --> 00:48:35,270 1560 00:48:35,270 --> 00:48:37,589 1561 00:48:37,589 --> 00:48:39,030 1562 00:48:39,030 --> 00:48:40,069 1563 00:48:40,069 --> 00:48:41,990 1564 00:48:41,990 --> 00:48:44,069 1565 00:48:44,069 --> 00:48:46,150 1566 00:48:46,150 --> 00:48:47,510 1567 00:48:47,510 --> 00:48:48,950 1568 00:48:48,950 --> 00:48:50,950 1569 00:48:50,950 --> 00:48:54,870 1570 00:48:54,870 --> 00:48:57,030 1571 00:48:57,030 --> 00:48:58,710 1572 00:48:58,710 --> 00:49:01,190 1573 00:49:01,190 --> 00:49:03,349 1574 00:49:03,349 --> 00:49:05,910 1575 00:49:05,910 --> 00:49:07,750 1576 00:49:07,750 --> 00:49:11,430 1577 00:49:11,430 --> 00:49:11,440 1578 00:49:11,440 --> 00:49:12,630 1579 00:49:12,630 --> 00:49:15,670 1580 00:49:15,670 --> 00:49:19,670 1581 00:49:19,670 --> 00:49:19,680 1582 00:49:19,680 --> 00:49:20,950 1583 00:49:20,950 --> 00:49:24,390 1584 00:49:24,390 --> 00:49:24,400 1585 00:49:24,400 --> 00:49:26,630 1586 00:49:26,630 --> 00:49:30,150 1587 00:49:30,150 --> 00:49:32,390 1588 00:49:32,390 --> 00:49:34,710 1589 00:49:34,710 --> 00:49:37,349 1590 00:49:37,349 --> 00:49:39,910 1591 00:49:39,910 --> 00:49:44,710 1592 00:49:44,710 --> 00:49:46,390 1593 00:49:46,390 --> 00:49:48,630 1594 00:49:48,630 --> 00:49:48,640 1595 00:49:48,640 --> 00:49:50,710 1596 00:49:50,710 --> 00:49:51,910 1597 00:49:51,910 --> 00:49:51,920 1598 00:49:51,920 --> 00:49:52,950 1599 00:49:52,950 --> 00:49:52,960 1600 00:49:52,960 --> 00:49:54,790 1601 00:49:54,790 --> 00:49:59,109 1602 00:49:59,109 --> 00:50:00,870 1603 00:50:00,870 --> 00:50:00,880 1604 00:50:00,880 --> 00:50:01,990 1605 00:50:01,990 --> 00:50:05,190 1606 00:50:05,190 --> 00:50:05,200 1607 00:50:05,200 --> 00:50:07,430 1608 00:50:07,430 --> 00:50:09,270 1609 00:50:09,270 --> 00:50:12,710 1610 00:50:12,710 --> 00:50:17,190 1611 00:50:17,190 --> 00:50:19,349 1612 00:50:19,349 --> 00:50:19,359 1613 00:50:19,359 --> 00:50:20,549 1614 00:50:20,549 --> 00:50:23,589 1615 00:50:23,589 --> 00:50:25,750 1616 00:50:25,750 --> 00:50:27,430 1617 00:50:27,430 --> 00:50:27,440 1618 00:50:27,440 --> 00:50:29,990 1619 00:50:29,990 --> 00:50:30,000 1620 00:50:30,000 --> 00:50:32,470 1621 00:50:32,470 --> 00:50:32,480 1622 00:50:32,480 --> 00:50:33,510 1623 00:50:33,510 --> 00:50:33,520 1624 00:50:33,520 --> 00:50:34,309 1625 00:50:34,309 --> 00:50:36,309 1626 00:50:36,309 --> 00:50:37,910 1627 00:50:37,910 --> 00:50:37,920 1628 00:50:37,920 --> 00:50:39,109 1629 00:50:39,109 --> 00:50:39,119 1630 00:50:39,119 --> 00:50:39,829 1631 00:50:39,829 --> 00:50:41,589 1632 00:50:41,589 --> 00:50:41,599 1633 00:50:41,599 --> 00:50:43,030 1634 00:50:43,030 --> 00:50:44,710 1635 00:50:44,710 --> 00:50:46,309 1636 00:50:46,309 --> 00:50:48,309 1637 00:50:48,309 --> 00:50:51,109 1638 00:50:51,109 --> 00:50:54,309 1639 00:50:54,309 --> 00:50:54,319 1640 00:50:54,319 --> 00:50:55,270 1641 00:50:55,270 --> 00:50:57,670 1642 00:50:57,670 --> 00:50:59,750 1643 00:50:59,750 --> 00:51:02,309 1644 00:51:02,309 --> 00:51:05,510 1645 00:51:05,510 --> 00:51:07,190 1646 00:51:07,190 --> 00:51:11,430 1647 00:51:11,430 --> 00:51:13,910 1648 00:51:13,910 --> 00:51:16,230 1649 00:51:16,230 --> 00:51:17,750 1650 00:51:17,750 --> 00:51:20,150 1651 00:51:20,150 --> 00:51:22,870 1652 00:51:22,870 --> 00:51:22,880 1653 00:51:22,880 --> 00:51:24,150 1654 00:51:24,150 --> 00:51:27,030 1655 00:51:27,030 --> 00:51:29,750 1656 00:51:29,750 --> 00:51:32,710 1657 00:51:32,710 --> 00:51:34,630 1658 00:51:34,630 --> 00:51:36,390 1659 00:51:36,390 --> 00:51:38,710 1660 00:51:38,710 --> 00:51:39,829 1661 00:51:39,829 --> 00:51:41,750 1662 00:51:41,750 --> 00:51:41,760 1663 00:51:41,760 --> 00:51:43,030 1664 00:51:43,030 --> 00:51:45,109 1665 00:51:45,109 --> 00:51:45,119 1666 00:51:45,119 --> 00:51:45,990 1667 00:51:45,990 --> 00:51:47,829 1668 00:51:47,829 --> 00:51:50,630 1669 00:51:50,630 --> 00:51:52,950 1670 00:51:52,950 --> 00:51:56,950 1671 00:51:56,950 --> 00:51:59,829 1672 00:51:59,829 --> 00:52:02,470 1673 00:52:02,470 --> 00:52:05,030 1674 00:52:05,030 --> 00:52:06,950 1675 00:52:06,950 --> 00:52:09,349 1676 00:52:09,349 --> 00:52:11,670 1677 00:52:11,670 --> 00:52:14,710 1678 00:52:14,710 --> 00:52:15,910 1679 00:52:15,910 --> 00:52:19,589 1680 00:52:19,589 --> 00:52:21,190 1681 00:52:21,190 --> 00:52:22,950 1682 00:52:22,950 --> 00:52:24,069 1683 00:52:24,069 --> 00:52:26,710 1684 00:52:26,710 --> 00:52:28,230 1685 00:52:28,230 --> 00:52:28,240 1686 00:52:28,240 --> 00:52:30,829 1687 00:52:30,829 --> 00:52:33,829 1688 00:52:33,829 --> 00:52:35,750 1689 00:52:35,750 --> 00:52:40,150 1690 00:52:40,150 --> 00:52:40,160 1691 00:52:40,160 --> 00:52:42,950 1692 00:52:42,950 --> 00:52:44,470 1693 00:52:44,470 --> 00:52:46,390 1694 00:52:46,390 --> 00:52:48,309 1695 00:52:48,309 --> 00:52:50,630 1696 00:52:50,630 --> 00:52:54,069 1697 00:52:54,069 --> 00:52:55,750 1698 00:52:55,750 --> 00:52:59,270 1699 00:52:59,270 --> 00:53:00,950 1700 00:53:00,950 --> 00:53:03,750 1701 00:53:03,750 --> 00:53:05,270 1702 00:53:05,270 --> 00:53:07,430 1703 00:53:07,430 --> 00:53:09,510 1704 00:53:09,510 --> 00:53:10,630 1705 00:53:10,630 --> 00:53:10,640 1706 00:53:10,640 --> 00:53:11,670 1707 00:53:11,670 --> 00:53:14,069 1708 00:53:14,069 --> 00:53:16,710 1709 00:53:16,710 --> 00:53:18,710 1710 00:53:18,710 --> 00:53:18,720 1711 00:53:18,720 --> 00:53:20,470 1712 00:53:20,470 --> 00:53:23,510 1713 00:53:23,510 --> 00:53:25,589 1714 00:53:25,589 --> 00:53:27,670 1715 00:53:27,670 --> 00:53:29,990 1716 00:53:29,990 --> 00:53:31,109 1717 00:53:31,109 --> 00:53:33,589 1718 00:53:33,589 --> 00:53:35,030 1719 00:53:35,030 --> 00:53:36,630 1720 00:53:36,630 --> 00:53:38,870 1721 00:53:38,870 --> 00:53:41,430 1722 00:53:41,430 --> 00:53:45,510 1723 00:53:45,510 --> 00:53:46,549 1724 00:53:46,549 --> 00:53:47,990 1725 00:53:47,990 --> 00:53:50,150 1726 00:53:50,150 --> 00:53:53,829 1727 00:53:53,829 --> 00:53:55,670 1728 00:53:55,670 --> 00:53:57,589 1729 00:53:57,589 --> 00:53:58,710 1730 00:53:58,710 --> 00:54:01,190 1731 00:54:01,190 --> 00:54:03,589 1732 00:54:03,589 --> 00:54:06,390 1733 00:54:06,390 --> 00:54:09,990 1734 00:54:09,990 --> 00:54:11,510 1735 00:54:11,510 --> 00:54:13,430 1736 00:54:13,430 --> 00:54:13,440 1737 00:54:13,440 --> 00:54:14,390 1738 00:54:14,390 --> 00:54:15,829 1739 00:54:15,829 --> 00:54:18,150 1740 00:54:18,150 --> 00:54:20,870 1741 00:54:20,870 --> 00:54:22,710 1742 00:54:22,710 --> 00:54:25,510 1743 00:54:25,510 --> 00:54:27,750 1744 00:54:27,750 --> 00:54:29,109 1745 00:54:29,109 --> 00:54:31,910 1746 00:54:31,910 --> 00:54:34,390 1747 00:54:34,390 --> 00:54:35,990 1748 00:54:35,990 --> 00:54:40,309 1749 00:54:40,309 --> 00:54:43,510 1750 00:54:43,510 --> 00:54:44,710 1751 00:54:44,710 --> 00:54:46,390 1752 00:54:46,390 --> 00:54:48,789 1753 00:54:48,789 --> 00:54:49,990 1754 00:54:49,990 --> 00:54:52,470 1755 00:54:52,470 --> 00:54:54,069 1756 00:54:54,069 --> 00:54:56,230 1757 00:54:56,230 --> 00:54:57,829 1758 00:54:57,829 --> 00:54:59,030 1759 00:54:59,030 --> 00:55:01,349 1760 00:55:01,349 --> 00:55:02,870 1761 00:55:02,870 --> 00:55:04,870 1762 00:55:04,870 --> 00:55:06,789 1763 00:55:06,789 --> 00:55:08,870 1764 00:55:08,870 --> 00:55:10,470 1765 00:55:10,470 --> 00:55:11,990 1766 00:55:11,990 --> 00:55:12,000 1767 00:55:12,000 --> 00:55:17,109 1768 00:55:17,109 --> 00:55:18,630 1769 00:55:18,630 --> 00:55:20,069 1770 00:55:20,069 --> 00:55:21,109 1771 00:55:21,109 --> 00:55:22,950 1772 00:55:22,950 --> 00:55:25,190 1773 00:55:25,190 --> 00:55:26,470 1774 00:55:26,470 --> 00:55:28,870 1775 00:55:28,870 --> 00:55:28,880 1776 00:55:28,880 --> 00:55:32,309 1777 00:55:32,309 --> 00:55:32,319 1778 00:55:32,319 --> 00:55:33,270 1779 00:55:33,270 --> 00:55:34,870 1780 00:55:34,870 --> 00:55:40,309 1781 00:55:40,309 --> 00:55:42,390 1782 00:55:42,390 --> 00:55:44,230 1783 00:55:44,230 --> 00:55:45,670 1784 00:55:45,670 --> 00:55:49,510 1785 00:55:49,510 --> 00:55:51,910 1786 00:55:51,910 --> 00:55:54,549 1787 00:55:54,549 --> 00:55:54,559 1788 00:55:54,559 --> 00:55:55,430 1789 00:55:55,430 --> 00:55:55,440 1790 00:55:55,440 --> 00:55:56,549 1791 00:55:56,549 --> 00:55:56,559 1792 00:55:56,559 --> 00:55:57,430 1793 00:55:57,430 --> 00:55:59,109 1794 00:55:59,109 --> 00:56:02,230 1795 00:56:02,230 --> 00:56:03,750 1796 00:56:03,750 --> 00:56:05,829 1797 00:56:05,829 --> 00:56:08,150 1798 00:56:08,150 --> 00:56:10,789 1799 00:56:10,789 --> 00:56:12,630 1800 00:56:12,630 --> 00:56:14,870 1801 00:56:14,870 --> 00:56:18,950 1802 00:56:18,950 --> 00:56:20,950 1803 00:56:20,950 --> 00:56:22,390 1804 00:56:22,390 --> 00:56:23,990 1805 00:56:23,990 --> 00:56:25,750 1806 00:56:25,750 --> 00:56:27,190 1807 00:56:27,190 --> 00:56:28,630 1808 00:56:28,630 --> 00:56:31,430 1809 00:56:31,430 --> 00:56:32,950 1810 00:56:32,950 --> 00:56:35,589 1811 00:56:35,589 --> 00:56:37,829 1812 00:56:37,829 --> 00:56:37,839 1813 00:56:37,839 --> 00:56:40,470 1814 00:56:40,470 --> 00:56:40,480 1815 00:56:40,480 --> 00:56:42,150 1816 00:56:42,150 --> 00:56:42,160 1817 00:56:42,160 --> 00:56:43,030 1818 00:56:43,030 --> 00:56:44,870 1819 00:56:44,870 --> 00:56:44,880 1820 00:56:44,880 --> 00:56:47,750 1821 00:56:47,750 --> 00:56:50,710 1822 00:56:50,710 --> 00:56:53,829 1823 00:56:53,829 --> 00:56:53,839 1824 00:56:53,839 --> 00:56:54,789 1825 00:56:54,789 --> 00:56:54,799 1826 00:56:54,799 --> 00:56:56,870 1827 00:56:56,870 --> 00:56:58,789 1828 00:56:58,789 --> 00:57:00,789 1829 00:57:00,789 --> 00:57:03,109 1830 00:57:03,109 --> 00:57:03,119 1831 00:57:03,119 --> 00:57:03,990 1832 00:57:03,990 --> 00:57:05,829 1833 00:57:05,829 --> 00:57:05,839 1834 00:57:05,839 --> 00:57:06,870 1835 00:57:06,870 --> 00:57:09,349 1836 00:57:09,349 --> 00:57:15,190 1837 00:57:15,190 --> 00:57:16,630 1838 00:57:16,630 --> 00:57:19,670 1839 00:57:19,670 --> 00:57:22,549 1840 00:57:22,549 --> 00:57:24,710 1841 00:57:24,710 --> 00:57:26,789 1842 00:57:26,789 --> 00:57:29,190 1843 00:57:29,190 --> 00:57:29,200 1844 00:57:29,200 --> 00:57:31,270 1845 00:57:31,270 --> 00:57:32,789 1846 00:57:32,789 --> 00:57:35,030 1847 00:57:35,030 --> 00:57:37,190 1848 00:57:37,190 --> 00:57:39,109 1849 00:57:39,109 --> 00:57:41,030 1850 00:57:41,030 --> 00:57:43,270 1851 00:57:43,270 --> 00:57:45,270 1852 00:57:45,270 --> 00:57:47,349 1853 00:57:47,349 --> 00:57:49,750 1854 00:57:49,750 --> 00:57:51,589 1855 00:57:51,589 --> 00:57:55,910 1856 00:57:55,910 --> 00:57:58,470 1857 00:57:58,470 --> 00:57:58,480 1858 00:57:58,480 --> 00:57:59,589 1859 00:57:59,589 --> 00:58:01,349 1860 00:58:01,349 --> 00:58:03,190 1861 00:58:03,190 --> 00:58:03,200 1862 00:58:03,200 --> 00:58:04,549 1863 00:58:04,549 --> 00:58:06,309 1864 00:58:06,309 --> 00:58:08,390 1865 00:58:08,390 --> 00:58:10,710 1866 00:58:10,710 --> 00:58:12,710 1867 00:58:12,710 --> 00:58:14,630 1868 00:58:14,630 --> 00:58:16,870 1869 00:58:16,870 --> 00:58:21,109 1870 00:58:21,109 --> 00:58:23,109 1871 00:58:23,109 --> 00:58:27,670 1872 00:58:27,670 --> 00:58:29,829 1873 00:58:29,829 --> 00:58:32,230 1874 00:58:32,230 --> 00:58:35,190 1875 00:58:35,190 --> 00:58:37,270 1876 00:58:37,270 --> 00:58:39,430 1877 00:58:39,430 --> 00:58:43,750 1878 00:58:43,750 --> 00:58:43,760 1879 00:58:43,760 --> 00:58:44,710 1880 00:58:44,710 --> 00:58:46,710 1881 00:58:46,710 --> 00:58:46,720 1882 00:58:46,720 --> 00:58:47,510 1883 00:58:47,510 --> 00:58:49,589 1884 00:58:49,589 --> 00:58:49,599 1885 00:58:49,599 --> 00:58:51,510 1886 00:58:51,510 --> 00:58:53,750 1887 00:58:53,750 --> 00:58:55,589 1888 00:58:55,589 --> 00:58:58,309 1889 00:58:58,309 --> 00:59:00,549 1890 00:59:00,549 --> 00:59:02,069 1891 00:59:02,069 --> 00:59:04,789 1892 00:59:04,789 --> 00:59:07,109 1893 00:59:07,109 --> 00:59:09,109 1894 00:59:09,109 --> 00:59:11,430 1895 00:59:11,430 --> 00:59:14,150 1896 00:59:14,150 --> 00:59:14,160 1897 00:59:14,160 --> 00:59:16,309 1898 00:59:16,309 --> 00:59:18,549 1899 00:59:18,549 --> 00:59:20,710 1900 00:59:20,710 --> 00:59:22,789 1901 00:59:22,789 --> 00:59:25,030 1902 00:59:25,030 --> 00:59:26,470 1903 00:59:26,470 --> 00:59:28,789 1904 00:59:28,789 --> 00:59:31,670 1905 00:59:31,670 --> 00:59:31,680 1906 00:59:31,680 --> 00:59:32,630 1907 00:59:32,630 --> 00:59:35,349 1908 00:59:35,349 --> 00:59:36,789 1909 00:59:36,789 --> 00:59:40,230 1910 00:59:40,230 --> 00:59:41,750 1911 00:59:41,750 --> 00:59:43,109 1912 00:59:43,109 --> 00:59:45,589 1913 00:59:45,589 --> 00:59:48,870 1914 00:59:48,870 --> 00:59:52,309 1915 00:59:52,309 --> 00:59:54,630 1916 00:59:54,630 --> 00:59:56,150 1917 00:59:56,150 --> 00:59:57,910 1918 00:59:57,910 --> 01:00:00,470 1919 01:00:00,470 --> 01:00:03,910 1920 01:00:03,910 --> 01:00:05,750 1921 01:00:05,750 --> 01:00:08,230 1922 01:00:08,230 --> 01:00:08,240 1923 01:00:08,240 --> 01:00:09,270 1924 01:00:09,270 --> 01:00:10,789 1925 01:00:10,789 --> 01:00:12,630 1926 01:00:12,630 --> 01:00:15,190 1927 01:00:15,190 --> 01:00:17,430 1928 01:00:17,430 --> 01:00:19,430 1929 01:00:19,430 --> 01:00:19,440 1930 01:00:19,440 --> 01:00:21,270 1931 01:00:21,270 --> 01:00:24,150 1932 01:00:24,150 --> 01:00:27,510 1933 01:00:27,510 --> 01:00:29,109 1934 01:00:29,109 --> 01:00:31,510 1935 01:00:31,510 --> 01:00:34,549 1936 01:00:34,549 --> 01:00:37,670 1937 01:00:37,670 --> 01:00:39,829 1938 01:00:39,829 --> 01:00:42,230 1939 01:00:42,230 --> 01:00:45,190 1940 01:00:45,190 --> 01:00:47,109 1941 01:00:47,109 --> 01:00:49,030 1942 01:00:49,030 --> 01:00:50,710 1943 01:00:50,710 --> 01:00:56,150 1944 01:00:56,150 --> 01:01:01,750 1945 01:01:01,750 --> 01:01:03,510 1946 01:01:03,510 --> 01:01:05,349 1947 01:01:05,349 --> 01:01:09,190 1948 01:01:09,190 --> 01:01:09,200 1949 01:01:09,200 --> 01:01:10,549 1950 01:01:10,549 --> 01:01:13,750 1951 01:01:13,750 --> 01:01:16,069 1952 01:01:16,069 --> 01:01:16,079 1953 01:01:16,079 --> 01:01:18,230 1954 01:01:18,230 --> 01:01:20,069 1955 01:01:20,069 --> 01:01:21,829 1956 01:01:21,829 --> 01:01:23,270 1957 01:01:23,270 --> 01:01:26,549 1958 01:01:26,549 --> 01:01:26,559 1959 01:01:26,559 --> 01:01:27,510 1960 01:01:27,510 --> 01:01:29,670 1961 01:01:29,670 --> 01:01:29,680 1962 01:01:29,680 --> 01:01:31,589 1963 01:01:31,589 --> 01:01:35,270 1964 01:01:35,270 --> 01:01:36,470 1965 01:01:36,470 --> 01:01:40,309 1966 01:01:40,309 --> 01:01:44,390 1967 01:01:44,390 --> 01:01:46,150 1968 01:01:46,150 --> 01:01:47,990 1969 01:01:47,990 --> 01:01:49,750 1970 01:01:49,750 --> 01:01:51,910 1971 01:01:51,910 --> 01:01:54,630 1972 01:01:54,630 --> 01:02:05,990 1973 01:02:05,990 --> 01:02:07,589 1974 01:02:07,589 --> 01:02:10,549 1975 01:02:10,549 --> 01:02:12,789 1976 01:02:12,789 --> 01:02:14,549 1977 01:02:14,549 --> 01:02:16,150 1978 01:02:16,150 --> 01:02:17,829 1979 01:02:17,829 --> 01:02:20,470 1980 01:02:20,470 --> 01:02:23,349 1981 01:02:23,349 --> 01:02:24,870 1982 01:02:24,870 --> 01:02:27,829 1983 01:02:27,829 --> 01:02:31,109 1984 01:02:31,109 --> 01:02:31,119 1985 01:02:31,119 --> 01:02:32,150 1986 01:02:32,150 --> 01:02:35,589 1987 01:02:35,589 --> 01:02:37,270 1988 01:02:37,270 --> 01:02:39,829 1989 01:02:39,829 --> 01:02:41,510 1990 01:02:41,510 --> 01:02:43,750 1991 01:02:43,750 --> 01:02:46,829 1992 01:02:46,829 --> 01:02:46,839 1993 01:02:46,839 --> 01:02:48,789 1994 01:02:48,789 --> 01:02:51,109 1995 01:02:51,109 --> 01:02:54,630 1996 01:02:54,630 --> 01:02:57,109 1997 01:02:57,109 --> 01:02:59,270 1998 01:02:59,270 --> 01:03:04,870 1999 01:03:04,870 --> 01:03:07,750 2000 01:03:07,750 --> 01:03:10,870 2001 01:03:10,870 --> 01:03:13,589 2002 01:03:13,589 --> 01:03:15,990 2003 01:03:15,990 --> 01:03:18,470 2004 01:03:18,470 --> 01:03:20,630 2005 01:03:20,630 --> 01:03:22,630 2006 01:03:22,630 --> 01:03:25,750 2007 01:03:25,750 --> 01:03:29,109 2008 01:03:29,109 --> 01:03:30,950 2009 01:03:30,950 --> 01:03:32,789 2010 01:03:32,789 --> 01:03:32,799 2011 01:03:32,799 --> 01:03:35,829 2012 01:03:35,829 --> 01:03:38,309 2013 01:03:38,309 --> 01:03:38,319 2014 01:03:38,319 --> 01:03:42,309 2015 01:03:42,309 --> 01:03:44,230 2016 01:03:44,230 --> 01:03:45,589 2017 01:03:45,589 --> 01:03:45,599 2018 01:03:45,599 --> 01:03:46,870 2019 01:03:46,870 --> 01:03:48,390 2020 01:03:48,390 --> 01:03:48,400 2021 01:03:48,400 --> 01:03:49,589 2022 01:03:49,589 --> 01:03:51,910 2023 01:03:51,910 --> 01:03:53,910 2024 01:03:53,910 --> 01:03:56,829 2025 01:03:56,829 --> 01:03:56,839 2026 01:03:56,839 --> 01:03:58,549 2027 01:03:58,549 --> 01:04:00,390 2028 01:04:00,390 --> 01:04:02,069 2029 01:04:02,069 --> 01:04:03,510 2030 01:04:03,510 --> 01:04:05,349 2031 01:04:05,349 --> 01:04:07,430 2032 01:04:07,430 --> 01:04:09,829 2033 01:04:09,829 --> 01:04:12,230 2034 01:04:12,230 --> 01:04:14,230 2035 01:04:14,230 --> 01:04:21,349 2036 01:04:21,349 --> 01:04:23,829 2037 01:04:23,829 --> 01:04:25,670 2038 01:04:25,670 --> 01:04:28,069 2039 01:04:28,069 --> 01:04:30,230 2040 01:04:30,230 --> 01:04:31,270 2041 01:04:31,270 --> 01:04:35,109 2042 01:04:35,109 --> 01:04:37,510 2043 01:04:37,510 --> 01:04:40,549 2044 01:04:40,549 --> 01:04:42,390 2045 01:04:42,390 --> 01:04:45,430 2046 01:04:45,430 --> 01:04:46,710 2047 01:04:46,710 --> 01:04:48,789 2048 01:04:48,789 --> 01:04:50,549 2049 01:04:50,549 --> 01:04:52,789 2050 01:04:52,789 --> 01:04:54,630 2051 01:04:54,630 --> 01:04:57,430 2052 01:04:57,430 --> 01:04:57,440 2053 01:04:57,440 --> 01:04:59,510 2054 01:04:59,510 --> 01:04:59,520 2055 01:04:59,520 --> 01:05:05,670 2056 01:05:05,670 --> 01:05:05,680 2057 01:05:05,680 --> 01:05:07,510 2058 01:05:07,510 --> 01:05:09,990 2059 01:05:09,990 --> 01:05:11,670 2060 01:05:11,670 --> 01:05:14,150 2061 01:05:14,150 --> 01:05:16,950 2062 01:05:16,950 --> 01:05:18,390 2063 01:05:18,390 --> 01:05:20,470 2064 01:05:20,470 --> 01:05:22,549 2065 01:05:22,549 --> 01:05:24,630 2066 01:05:24,630 --> 01:05:27,029 2067 01:05:27,029 --> 01:05:28,390 2068 01:05:28,390 --> 01:05:30,230 2069 01:05:30,230 --> 01:05:32,950 2070 01:05:32,950 --> 01:05:32,960 2071 01:05:32,960 --> 01:05:34,309 2072 01:05:34,309 --> 01:05:36,789 2073 01:05:36,789 --> 01:05:39,990 2074 01:05:39,990 --> 01:05:42,470 2075 01:05:42,470 --> 01:05:45,270 2076 01:05:45,270 --> 01:05:47,750 2077 01:05:47,750 --> 01:05:49,029 2078 01:05:49,029 --> 01:05:51,349 2079 01:05:51,349 --> 01:05:52,950 2080 01:05:52,950 --> 01:05:56,950 2081 01:05:56,950 --> 01:05:56,960 2082 01:05:56,960 --> 01:05:59,670 2083 01:05:59,670 --> 01:06:01,670 2084 01:06:01,670 --> 01:06:04,230 2085 01:06:04,230 --> 01:06:06,150 2086 01:06:06,150 --> 01:06:07,670 2087 01:06:07,670 --> 01:06:11,990 2088 01:06:11,990 --> 01:06:12,000 2089 01:06:12,000 --> 01:06:16,950 2090 01:06:16,950 --> 01:06:18,630 2091 01:06:18,630 --> 01:06:19,990 2092 01:06:19,990 --> 01:06:21,829 2093 01:06:21,829 --> 01:06:23,430 2094 01:06:23,430 --> 01:06:23,440 2095 01:06:23,440 --> 01:06:24,150 2096 01:06:24,150 --> 01:06:27,430 2097 01:06:27,430 --> 01:06:27,440 2098 01:06:27,440 --> 01:06:29,430 2099 01:06:29,430 --> 01:06:31,910 2100 01:06:31,910 --> 01:06:35,829 2101 01:06:35,829 --> 01:06:38,309 2102 01:06:38,309 --> 01:06:40,150 2103 01:06:40,150 --> 01:06:41,349 2104 01:06:41,349 --> 01:06:43,430 2105 01:06:43,430 --> 01:06:44,789 2106 01:06:44,789 --> 01:06:52,710 2107 01:06:52,710 --> 01:06:54,069 2108 01:06:54,069 --> 01:06:56,230 2109 01:06:56,230 --> 01:06:58,789 2110 01:06:58,789 --> 01:07:00,870 2111 01:07:00,870 --> 01:07:02,390 2112 01:07:02,390 --> 01:07:04,309 2113 01:07:04,309 --> 01:07:06,390 2114 01:07:06,390 --> 01:07:08,390 2115 01:07:08,390 --> 01:07:08,400 2116 01:07:08,400 --> 01:07:10,710 2117 01:07:10,710 --> 01:07:10,720 2118 01:07:10,720 --> 01:07:17,029 2119 01:07:17,029 --> 01:07:18,789 2120 01:07:18,789 --> 01:07:19,910 2121 01:07:19,910 --> 01:07:23,349 2122 01:07:23,349 --> 01:07:25,430 2123 01:07:25,430 --> 01:07:27,829 2124 01:07:27,829 --> 01:07:27,839 2125 01:07:27,839 --> 01:07:29,190 2126 01:07:29,190 --> 01:07:31,990 2127 01:07:31,990 --> 01:07:34,309 2128 01:07:34,309 --> 01:07:36,710 2129 01:07:36,710 --> 01:07:38,390 2130 01:07:38,390 --> 01:07:42,230 2131 01:07:42,230 --> 01:07:43,990 2132 01:07:43,990 --> 01:07:46,309 2133 01:07:46,309 --> 01:07:48,390 2134 01:07:48,390 --> 01:07:50,390 2135 01:07:50,390 --> 01:07:50,400 2136 01:07:50,400 --> 01:07:51,670 2137 01:07:51,670 --> 01:07:53,589 2138 01:07:53,589 --> 01:07:55,109 2139 01:07:55,109 --> 01:07:55,119 2140 01:07:55,119 --> 01:07:56,710 2141 01:07:56,710 --> 01:07:56,720 2142 01:07:56,720 --> 01:07:57,670 2143 01:07:57,670 --> 01:07:59,670 2144 01:07:59,670 --> 01:08:01,349 2145 01:08:01,349 --> 01:08:03,029 2146 01:08:03,029 --> 01:08:06,230 2147 01:08:06,230 --> 01:08:07,430 2148 01:08:07,430 --> 01:08:11,750 2149 01:08:11,750 --> 01:08:13,910 2150 01:08:13,910 --> 01:08:17,349 2151 01:08:17,349 --> 01:08:19,910 2152 01:08:19,910 --> 01:08:19,920 2153 01:08:19,920 --> 01:08:20,709 2154 01:08:20,709 --> 01:08:22,789 2155 01:08:22,789 --> 01:08:24,630 2156 01:08:24,630 --> 01:08:27,590 2157 01:08:27,590 --> 01:08:29,110 2158 01:08:29,110 --> 01:08:31,430 2159 01:08:31,430 --> 01:08:33,269 2160 01:08:33,269 --> 01:08:33,279 2161 01:08:33,279 --> 01:08:34,630 2162 01:08:34,630 --> 01:08:37,269 2163 01:08:37,269 --> 01:08:38,390 2164 01:08:38,390 --> 01:08:40,390 2165 01:08:40,390 --> 01:08:41,910 2166 01:08:41,910 --> 01:08:43,269 2167 01:08:43,269 --> 01:08:43,279 2168 01:08:43,279 --> 01:08:44,950 2169 01:08:44,950 --> 01:08:45,990 2170 01:08:45,990 --> 01:08:48,390 2171 01:08:48,390 --> 01:08:51,510 2172 01:08:51,510 --> 01:08:51,520 2173 01:08:51,520 --> 01:08:53,030 2174 01:08:53,030 --> 01:08:55,829 2175 01:08:55,829 --> 01:08:58,229 2176 01:08:58,229 --> 01:09:01,110 2177 01:09:01,110 --> 01:09:02,630 2178 01:09:02,630 --> 01:09:04,390 2179 01:09:04,390 --> 01:09:05,829 2180 01:09:05,829 --> 01:09:07,829 2181 01:09:07,829 --> 01:09:09,590 2182 01:09:09,590 --> 01:09:12,630 2183 01:09:12,630 --> 01:09:15,349 2184 01:09:15,349 --> 01:09:18,789 2185 01:09:18,789 --> 01:09:18,799 2186 01:09:18,799 --> 01:09:19,829 2187 01:09:19,829 --> 01:09:21,430 2188 01:09:21,430 --> 01:09:23,990 2189 01:09:23,990 --> 01:09:27,189 2190 01:09:27,189 --> 01:09:27,199 2191 01:09:27,199 --> 01:09:28,470 2192 01:09:28,470 --> 01:09:30,070 2193 01:09:30,070 --> 01:09:31,829 2194 01:09:31,829 --> 01:09:33,269 2195 01:09:33,269 --> 01:09:35,590 2196 01:09:35,590 --> 01:09:35,600 2197 01:09:35,600 --> 01:09:37,430 2198 01:09:37,430 --> 01:09:40,470 2199 01:09:40,470 --> 01:09:44,309 2200 01:09:44,309 --> 01:09:44,319 2201 01:09:44,319 --> 01:09:45,189 2202 01:09:45,189 --> 01:09:47,590 2203 01:09:47,590 --> 01:09:50,709 2204 01:09:50,709 --> 01:09:52,470 2205 01:09:52,470 --> 01:09:55,750 2206 01:09:55,750 --> 01:09:58,229 2207 01:09:58,229 --> 01:09:59,990 2208 01:09:59,990 --> 01:10:00,000 2209 01:10:00,000 --> 01:10:01,189 2210 01:10:01,189 --> 01:10:04,310 2211 01:10:04,310 --> 01:10:05,590 2212 01:10:05,590 --> 01:10:07,990 2213 01:10:07,990 --> 01:10:10,550 2214 01:10:10,550 --> 01:10:11,510 2215 01:10:11,510 --> 01:10:13,669 2216 01:10:13,669 --> 01:10:15,189 2217 01:10:15,189 --> 01:10:15,199 2218 01:10:15,199 --> 01:10:17,750 2219 01:10:17,750 --> 01:10:19,910 2220 01:10:19,910 --> 01:10:19,920 2221 01:10:19,920 --> 01:10:23,030 2222 01:10:23,030 --> 01:10:24,630 2223 01:10:24,630 --> 01:10:24,640 2224 01:10:24,640 --> 01:10:25,669 2225 01:10:25,669 --> 01:10:27,750 2226 01:10:27,750 --> 01:10:29,830 2227 01:10:29,830 --> 01:10:32,070 2228 01:10:32,070 --> 01:10:34,950 2229 01:10:34,950 --> 01:10:35,990 2230 01:10:35,990 --> 01:10:37,430 2231 01:10:37,430 --> 01:10:39,990 2232 01:10:39,990 --> 01:10:42,830 2233 01:10:42,830 --> 01:10:45,750 2234 01:10:45,750 --> 01:10:47,910 2235 01:10:47,910 --> 01:10:50,790 2236 01:10:50,790 --> 01:10:53,350 2237 01:10:53,350 --> 01:10:53,360 2238 01:10:53,360 --> 01:10:54,149 2239 01:10:54,149 --> 01:10:56,390 2240 01:10:56,390 --> 01:10:58,630 2241 01:10:58,630 --> 01:11:00,470 2242 01:11:00,470 --> 01:11:00,480 2243 01:11:00,480 --> 01:11:01,510 2244 01:11:01,510 --> 01:11:01,520 2245 01:11:01,520 --> 01:11:02,709 2246 01:11:02,709 --> 01:11:04,310 2247 01:11:04,310 --> 01:11:06,149 2248 01:11:06,149 --> 01:11:06,159 2249 01:11:06,159 --> 01:11:07,510 2250 01:11:07,510 --> 01:11:09,189 2251 01:11:09,189 --> 01:11:11,350 2252 01:11:11,350 --> 01:11:13,750 2253 01:11:13,750 --> 01:11:16,470 2254 01:11:16,470 --> 01:11:16,480 2255 01:11:16,480 --> 01:11:17,830 2256 01:11:17,830 --> 01:11:17,840 2257 01:11:17,840 --> 01:11:18,950 2258 01:11:18,950 --> 01:11:20,950 2259 01:11:20,950 --> 01:11:22,630 2260 01:11:22,630 --> 01:11:24,790 2261 01:11:24,790 --> 01:11:29,270 2262 01:11:29,270 --> 01:11:31,510 2263 01:11:31,510 --> 01:11:33,030 2264 01:11:33,030 --> 01:11:33,040 2265 01:11:33,040 --> 01:11:33,750 2266 01:11:33,750 --> 01:11:34,950 2267 01:11:34,950 --> 01:11:34,960 2268 01:11:34,960 --> 01:11:36,070 2269 01:11:36,070 --> 01:11:37,270 2270 01:11:37,270 --> 01:11:38,870 2271 01:11:38,870 --> 01:11:40,550 2272 01:11:40,550 --> 01:11:40,560 2273 01:11:40,560 --> 01:11:41,270 2274 01:11:41,270 --> 01:11:43,189 2275 01:11:43,189 --> 01:11:44,870 2276 01:11:44,870 --> 01:11:44,880 2277 01:11:44,880 --> 01:11:45,750 2278 01:11:45,750 --> 01:11:45,760 2279 01:11:45,760 --> 01:11:48,390 2280 01:11:48,390 --> 01:11:48,400 2281 01:11:48,400 --> 01:11:49,270 2282 01:11:49,270 --> 01:11:51,030 2283 01:11:51,030 --> 01:11:53,430 2284 01:11:53,430 --> 01:11:55,030 2285 01:11:55,030 --> 01:11:56,630 2286 01:11:56,630 --> 01:11:59,189 2287 01:11:59,189 --> 01:11:59,199 2288 01:11:59,199 --> 01:12:00,310 2289 01:12:00,310 --> 01:12:01,990 2290 01:12:01,990 --> 01:12:03,669 2291 01:12:03,669 --> 01:12:07,189 2292 01:12:07,189 --> 01:12:10,149 2293 01:12:10,149 --> 01:12:11,830 2294 01:12:11,830 --> 01:12:13,510 2295 01:12:13,510 --> 01:12:15,430 2296 01:12:15,430 --> 01:12:18,630 2297 01:12:18,630 --> 01:12:21,590 2298 01:12:21,590 --> 01:12:23,510 2299 01:12:23,510 --> 01:12:25,750 2300 01:12:25,750 --> 01:12:27,189 2301 01:12:27,189 --> 01:12:29,990 2302 01:12:29,990 --> 01:12:30,000 2303 01:12:30,000 --> 01:12:31,189 2304 01:12:31,189 --> 01:12:33,830 2305 01:12:33,830 --> 01:12:34,950 2306 01:12:34,950 --> 01:12:36,630 2307 01:12:36,630 --> 01:12:39,189 2308 01:12:39,189 --> 01:12:42,149 2309 01:12:42,149 --> 01:12:43,910 2310 01:12:43,910 --> 01:12:45,990 2311 01:12:45,990 --> 01:12:48,709 2312 01:12:48,709 --> 01:12:50,149 2313 01:12:50,149 --> 01:12:50,159 2314 01:12:50,159 --> 01:12:51,590 2315 01:12:51,590 --> 01:12:51,600 2316 01:12:51,600 --> 01:12:53,350 2317 01:12:53,350 --> 01:12:55,270 2318 01:12:55,270 --> 01:12:57,030 2319 01:12:57,030 --> 01:12:57,040 2320 01:12:57,040 --> 01:12:58,070 2321 01:12:58,070 --> 01:13:00,950 2322 01:13:00,950 --> 01:13:04,149 2323 01:13:04,149 --> 01:13:05,830 2324 01:13:05,830 --> 01:13:05,840 2325 01:13:05,840 --> 01:13:07,750 2326 01:13:07,750 --> 01:13:09,510 2327 01:13:09,510 --> 01:13:11,910 2328 01:13:11,910 --> 01:13:13,590 2329 01:13:13,590 --> 01:13:14,870 2330 01:13:14,870 --> 01:13:14,880 2331 01:13:14,880 --> 01:13:17,510 2332 01:13:17,510 --> 01:13:19,910 2333 01:13:19,910 --> 01:13:21,510 2334 01:13:21,510 --> 01:13:23,990 2335 01:13:23,990 --> 01:13:26,149 2336 01:13:26,149 --> 01:13:29,030 2337 01:13:29,030 --> 01:13:30,630 2338 01:13:30,630 --> 01:13:32,149 2339 01:13:32,149 --> 01:13:35,110 2340 01:13:35,110 --> 01:13:37,350 2341 01:13:37,350 --> 01:13:38,950 2342 01:13:38,950 --> 01:13:41,030 2343 01:13:41,030 --> 01:13:42,630 2344 01:13:42,630 --> 01:13:44,390 2345 01:13:44,390 --> 01:13:46,470 2346 01:13:46,470 --> 01:13:47,990 2347 01:13:47,990 --> 01:13:50,790 2348 01:13:50,790 --> 01:13:52,870 2349 01:13:52,870 --> 01:13:55,189 2350 01:13:55,189 --> 01:13:57,110 2351 01:13:57,110 --> 01:13:58,709 2352 01:13:58,709 --> 01:13:58,719 2353 01:13:58,719 --> 01:13:59,430 2354 01:13:59,430 --> 01:14:01,830 2355 01:14:01,830 --> 01:14:03,270 2356 01:14:03,270 --> 01:14:05,189 2357 01:14:05,189 --> 01:14:07,110 2358 01:14:07,110 --> 01:14:08,310 2359 01:14:08,310 --> 01:14:10,229 2360 01:14:10,229 --> 01:14:12,870 2361 01:14:12,870 --> 01:14:15,510 2362 01:14:15,510 --> 01:14:15,520 2363 01:14:15,520 --> 01:14:16,470 2364 01:14:16,470 --> 01:14:18,070 2365 01:14:18,070 --> 01:14:20,149 2366 01:14:20,149 --> 01:14:22,070 2367 01:14:22,070 --> 01:14:24,550 2368 01:14:24,550 --> 01:14:26,709 2369 01:14:26,709 --> 01:14:28,950 2370 01:14:28,950 --> 01:14:31,110 2371 01:14:31,110 --> 01:14:32,470 2372 01:14:32,470 --> 01:14:34,790 2373 01:14:34,790 --> 01:14:36,630 2374 01:14:36,630 --> 01:14:38,149 2375 01:14:38,149 --> 01:14:38,159 2376 01:14:38,159 --> 01:14:38,950 2377 01:14:38,950 --> 01:14:40,790 2378 01:14:40,790 --> 01:14:42,550 2379 01:14:42,550 --> 01:14:43,910 2380 01:14:43,910 --> 01:14:45,590 2381 01:14:45,590 --> 01:14:49,350 2382 01:14:49,350 --> 01:14:49,360 2383 01:14:49,360 --> 01:14:50,709 2384 01:14:50,709 --> 01:14:52,950 2385 01:14:52,950 --> 01:14:53,990 2386 01:14:53,990 --> 01:14:56,310 2387 01:14:56,310 --> 01:14:57,910 2388 01:14:57,910 --> 01:14:59,430 2389 01:14:59,430 --> 01:15:00,950 2390 01:15:00,950 --> 01:15:03,189 2391 01:15:03,189 --> 01:15:05,270 2392 01:15:05,270 --> 01:15:07,030 2393 01:15:07,030 --> 01:15:07,040 2394 01:15:07,040 --> 01:15:08,470 2395 01:15:08,470 --> 01:15:09,990 2396 01:15:09,990 --> 01:15:11,270 2397 01:15:11,270 --> 01:15:11,280 2398 01:15:11,280 --> 01:15:12,790 2399 01:15:12,790 --> 01:15:14,070 2400 01:15:14,070 --> 01:15:15,590 2401 01:15:15,590 --> 01:15:17,189 2402 01:15:17,189 --> 01:15:19,110 2403 01:15:19,110 --> 01:15:19,120 2404 01:15:19,120 --> 01:15:20,630 2405 01:15:20,630 --> 01:15:23,189 2406 01:15:23,189 --> 01:15:25,110 2407 01:15:25,110 --> 01:15:27,189 2408 01:15:27,189 --> 01:15:28,709 2409 01:15:28,709 --> 01:15:30,149 2410 01:15:30,149 --> 01:15:30,159 2411 01:15:30,159 --> 01:15:31,270 2412 01:15:31,270 --> 01:15:32,790 2413 01:15:32,790 --> 01:15:35,110 2414 01:15:35,110 --> 01:15:37,590 2415 01:15:37,590 --> 01:15:39,910 2416 01:15:39,910 --> 01:15:41,110 2417 01:15:41,110 --> 01:15:42,550 2418 01:15:42,550 --> 01:15:42,560 2419 01:15:42,560 --> 01:15:44,390 2420 01:15:44,390 --> 01:15:45,750 2421 01:15:45,750 --> 01:15:47,510 2422 01:15:47,510 --> 01:15:47,520 2423 01:15:47,520 --> 01:15:48,550 2424 01:15:48,550 --> 01:15:48,560 2425 01:15:48,560 --> 01:15:50,870 2426 01:15:50,870 --> 01:15:52,870 2427 01:15:52,870 --> 01:15:54,950 2428 01:15:54,950 --> 01:15:56,870 2429 01:15:56,870 --> 01:15:58,709 2430 01:15:58,709 --> 01:15:58,719 2431 01:15:58,719 --> 01:16:01,030 2432 01:16:01,030 --> 01:16:01,940 2433 01:16:01,940 --> 01:16:01,950 2434 01:16:01,950 --> 01:16:04,830 2435 01:16:04,830 --> 01:16:07,669 2436 01:16:07,669 --> 01:16:10,070 2437 01:16:10,070 --> 01:16:12,870 2438 01:16:12,870 --> 01:16:15,270 2439 01:16:15,270 --> 01:16:19,590 2440 01:16:19,590 --> 01:16:19,600 2441 01:16:19,600 --> 01:16:22,310 2442 01:16:22,310 --> 01:16:24,870 2443 01:16:24,870 --> 01:16:26,390 2444 01:16:26,390 --> 01:16:27,910 2445 01:16:27,910 --> 01:16:29,830 2446 01:16:29,830 --> 01:16:32,550 2447 01:16:32,550 --> 01:16:35,430 2448 01:16:35,430 --> 01:16:37,030 2449 01:16:37,030 --> 01:16:38,870 2450 01:16:38,870 --> 01:16:40,149 2451 01:16:40,149 --> 01:16:42,630 2452 01:16:42,630 --> 01:16:45,110 2453 01:16:45,110 --> 01:16:47,669 2454 01:16:47,669 --> 01:16:48,950 2455 01:16:48,950 --> 01:16:50,390 2456 01:16:50,390 --> 01:16:51,910 2457 01:16:51,910 --> 01:16:51,920 2458 01:16:51,920 --> 01:16:52,870 2459 01:16:52,870 --> 01:16:54,550 2460 01:16:54,550 --> 01:16:57,510 2461 01:16:57,510 --> 01:17:01,910 2462 01:17:01,910 --> 01:17:03,990 2463 01:17:03,990 --> 01:17:04,000 2464 01:17:04,000 --> 01:17:05,430 2465 01:17:05,430 --> 01:17:08,470 2466 01:17:08,470 --> 01:17:10,470 2467 01:17:10,470 --> 01:17:16,229 2468 01:17:16,229 --> 01:17:24,550 2469 01:17:24,550 --> 01:17:28,070 2470 01:17:28,070 --> 01:17:29,990 2471 01:17:29,990 --> 01:17:32,790 2472 01:17:32,790 --> 01:17:34,630 2473 01:17:34,630 --> 01:17:35,750 2474 01:17:35,750 --> 01:17:37,750 2475 01:17:37,750 --> 01:17:39,350 2476 01:17:39,350 --> 01:17:39,360 2477 01:17:39,360 --> 01:17:41,189 2478 01:17:41,189 --> 01:17:46,709 2479 01:17:46,709 --> 01:17:49,110 2480 01:17:49,110 --> 01:17:51,750 2481 01:17:51,750 --> 01:17:53,990 2482 01:17:53,990 --> 01:17:55,750 2483 01:17:55,750 --> 01:17:58,630 2484 01:17:58,630 --> 01:18:00,310 2485 01:18:00,310 --> 01:18:02,149 2486 01:18:02,149 --> 01:18:02,159 2487 01:18:02,159 --> 01:18:04,070 2488 01:18:04,070 --> 01:18:06,229 2489 01:18:06,229 --> 01:18:08,870 2490 01:18:08,870 --> 01:18:10,709 2491 01:18:10,709 --> 01:18:14,470 2492 01:18:14,470 --> 01:18:14,480 2493 01:18:14,480 --> 01:18:15,510 2494 01:18:15,510 --> 01:18:17,910 2495 01:18:17,910 --> 01:18:20,070 2496 01:18:20,070 --> 01:18:21,830 2497 01:18:21,830 --> 01:18:23,030 2498 01:18:23,030 --> 01:18:26,630 2499 01:18:26,630 --> 01:18:26,640 2500 01:18:26,640 --> 01:18:27,750 2501 01:18:27,750 --> 01:18:30,630 2502 01:18:30,630 --> 01:18:34,550 2503 01:18:34,550 --> 01:18:37,430 2504 01:18:37,430 --> 01:18:39,350 2505 01:18:39,350 --> 01:18:41,110 2506 01:18:41,110 --> 01:18:43,350 2507 01:18:43,350 --> 01:18:43,360 2508 01:18:43,360 --> 01:18:44,709 2509 01:18:44,709 --> 01:18:47,110 2510 01:18:47,110 --> 01:18:48,950 2511 01:18:48,950 --> 01:18:51,110 2512 01:18:51,110 --> 01:18:51,120 2513 01:18:51,120 --> 01:18:52,070 2514 01:18:52,070 --> 01:18:54,950 2515 01:18:54,950 --> 01:18:57,510 2516 01:18:57,510 --> 01:19:00,229 2517 01:19:00,229 --> 01:19:02,950 2518 01:19:02,950 --> 01:19:05,030 2519 01:19:05,030 --> 01:19:06,310 2520 01:19:06,310 --> 01:19:08,790 2521 01:19:08,790 --> 01:19:10,149 2522 01:19:10,149 --> 01:19:11,430 2523 01:19:11,430 --> 01:19:14,229 2524 01:19:14,229 --> 01:19:14,239 2525 01:19:14,239 --> 01:19:15,750 2526 01:19:15,750 --> 01:19:18,229 2527 01:19:18,229 --> 01:19:19,910 2528 01:19:19,910 --> 01:19:21,990 2529 01:19:21,990 --> 01:19:24,149 2530 01:19:24,149 --> 01:19:25,669 2531 01:19:25,669 --> 01:19:25,679 2532 01:19:25,679 --> 01:19:26,790 2533 01:19:26,790 --> 01:19:29,270 2534 01:19:29,270 --> 01:19:29,280 2535 01:19:29,280 --> 01:19:31,189 2536 01:19:31,189 --> 01:19:35,669 2537 01:19:35,669 --> 01:19:37,270 2538 01:19:37,270 --> 01:19:38,790 2539 01:19:38,790 --> 01:19:40,950 2540 01:19:40,950 --> 01:19:43,510 2541 01:19:43,510 --> 01:19:45,430 2542 01:19:45,430 --> 01:19:48,149 2543 01:19:48,149 --> 01:19:48,159 2544 01:19:48,159 --> 01:19:53,270 2545 01:19:53,270 --> 01:19:56,390 2546 01:19:56,390 --> 01:19:58,870 2547 01:19:58,870 --> 01:20:01,110 2548 01:20:01,110 --> 01:20:02,950 2549 01:20:02,950 --> 01:20:05,750 2550 01:20:05,750 --> 01:20:05,760 2551 01:20:05,760 --> 01:20:06,709 2552 01:20:06,709 --> 01:20:09,189 2553 01:20:09,189 --> 01:20:12,390 2554 01:20:12,390 --> 01:20:14,229 2555 01:20:14,229 --> 01:20:15,669 2556 01:20:15,669 --> 01:20:17,910 2557 01:20:17,910 --> 01:20:17,920 2558 01:20:17,920 --> 01:20:20,629 2559 01:20:20,629 --> 01:20:22,870 2560 01:20:22,870 --> 01:20:25,350 2561 01:20:25,350 --> 01:20:27,270 2562 01:20:27,270 --> 01:20:29,910 2563 01:20:29,910 --> 01:20:31,270 2564 01:20:31,270 --> 01:20:33,590 2565 01:20:33,590 --> 01:20:33,600 2566 01:20:33,600 --> 01:20:34,870 2567 01:20:34,870 --> 01:20:36,790 2568 01:20:36,790 --> 01:20:40,149 2569 01:20:40,149 --> 01:20:41,830 2570 01:20:41,830 --> 01:20:44,229 2571 01:20:44,229 --> 01:20:45,669 2572 01:20:45,669 --> 01:20:47,830 2573 01:20:47,830 --> 01:20:50,790 2574 01:20:50,790 --> 01:20:52,310 2575 01:20:52,310 --> 01:20:53,510 2576 01:20:53,510 --> 01:20:54,950 2577 01:20:54,950 --> 01:20:56,790 2578 01:20:56,790 --> 01:20:58,550 2579 01:20:58,550 --> 01:21:00,550 2580 01:21:00,550 --> 01:21:02,149 2581 01:21:02,149 --> 01:21:04,070 2582 01:21:04,070 --> 01:21:05,910 2583 01:21:05,910 --> 01:21:07,270 2584 01:21:07,270 --> 01:21:09,990 2585 01:21:09,990 --> 01:21:11,590 2586 01:21:11,590 --> 01:21:12,830 2587 01:21:12,830 --> 01:21:15,430 2588 01:21:15,430 --> 01:21:17,030 2589 01:21:17,030 --> 01:21:18,709 2590 01:21:18,709 --> 01:21:20,709 2591 01:21:20,709 --> 01:21:22,550 2592 01:21:22,550 --> 01:21:24,870 2593 01:21:24,870 --> 01:21:24,880 2594 01:21:24,880 --> 01:21:27,510 2595 01:21:27,510 --> 01:21:29,270 2596 01:21:29,270 --> 01:21:31,590 2597 01:21:31,590 --> 01:21:33,510 2598 01:21:33,510 --> 01:21:35,270 2599 01:21:35,270 --> 01:21:36,550 2600 01:21:36,550 --> 01:21:37,830 2601 01:21:37,830 --> 01:21:40,950 2602 01:21:40,950 --> 01:21:44,229 2603 01:21:44,229 --> 01:21:46,550 2604 01:21:46,550 --> 01:21:49,110 2605 01:21:49,110 --> 01:21:51,270 2606 01:21:51,270 --> 01:21:54,470 2607 01:21:54,470 --> 01:21:56,870 2608 01:21:56,870 --> 01:21:58,629 2609 01:21:58,629 --> 01:22:01,510 2610 01:22:01,510 --> 01:22:03,590 2611 01:22:03,590 --> 01:22:05,030 2612 01:22:05,030 --> 01:22:06,790 2613 01:22:06,790 --> 01:22:07,990 2614 01:22:07,990 --> 01:22:11,669 2615 01:22:11,669 --> 01:22:13,270 2616 01:22:13,270 --> 01:22:14,950 2617 01:22:14,950 --> 01:22:17,750 2618 01:22:17,750 --> 01:22:19,430 2619 01:22:19,430 --> 01:22:20,709 2620 01:22:20,709 --> 01:22:22,550 2621 01:22:22,550 --> 01:22:24,070 2622 01:22:24,070 --> 01:22:25,910 2623 01:22:25,910 --> 01:22:27,669 2624 01:22:27,669 --> 01:22:30,950 2625 01:22:30,950 --> 01:22:33,430 2626 01:22:33,430 --> 01:22:35,110 2627 01:22:35,110 --> 01:22:38,470 2628 01:22:38,470 --> 01:22:40,070 2629 01:22:40,070 --> 01:22:42,070 2630 01:22:42,070 --> 01:22:44,070 2631 01:22:44,070 --> 01:22:46,149 2632 01:22:46,149 --> 01:22:46,159 2633 01:22:46,159 --> 01:22:49,430 2634 01:22:49,430 --> 01:22:50,709 2635 01:22:50,709 --> 01:22:51,910 2636 01:22:51,910 --> 01:22:53,350 2637 01:22:53,350 --> 01:22:56,470 2638 01:22:56,470 --> 01:22:58,550 2639 01:22:58,550 --> 01:22:58,560 2640 01:22:58,560 --> 01:23:00,470 2641 01:23:00,470 --> 01:23:03,350 2642 01:23:03,350 --> 01:23:05,669 2643 01:23:05,669 --> 01:23:08,629 2644 01:23:08,629 --> 01:23:28,870 2645 01:23:28,870 --> 01:23:28,880 2646 01:23:28,880 --> 01:23:30,960