
Title:
0805 Snapshots

Description:

What this means is not for any given number of variables,

we can write a Boolean formula

that can be satisfied

if and only if exactly what one of these variables is set to true,

and we figure out that we can do this for any number of variables that we want.

So now let's go back to snapshots

and see what the Boolean formula

that I just showed you has to do with these snapshots.

Each snapshot, as we've said, basically consists of

3 components, so we have the read only number here,

which is basically the input.

We have program, and we have the readwrite memory

for immediate results and output.

So now let's think back a moment of how we defined the RAM.

When we defined the RAM in the last unit,

what we said was the following.

We said that whenever we're talking about memory,

so this part here or this part here,

then every single cell in the memory can not hold

arbitrarily large variables,

which means, for example, that

this cell here could either be 0;

it could be 1, it could be 2, and so on,

but there's a certain limit of how large those values here can be,

just as with your novel computer programs, too.

They can carry very, very large numbers

but there's a limit

and that limit is some constant,

so I'll just write c here, so if you have an 8bit computer,

that constant will be smaller, of course, than if you have a 16bit computer

and so on, but in any case,

it will be some constant determined by the machine,

and the same thing is going to be true all along the memory.

So for each single memory cell

that you have here,

you have a constant number of possibilities

for the values that this memory cell can take,

so the size here is constant,

and here, it's polynomial in n,

as we figured out before.

Now what about the program?

So for the program, we said that,

of course the size of the program of the algorithm

does not change with the size of the input,

so if you look at the program and your write it

as we said, we've written the code from left to right,

but normally, you'll write it from top to bottom,

so if you took this code and wrote it like this,

then you would have a constant number of lines in your program

and that would be a certain position on where you are,

so again here,

there's a constant number of potential positions where you can be in the code,

and of course, you just have one code,

so there's no polynomial size here.

It's just a constant number of code lines.

And finally, over here fr the input;

of course this is read only, but what I'm interested in

is again the possible number of states

that you can have in each of these memory cells,

and that again is the same constant as over here,

and here we have again a polynomial in n,

so what does this have to do with the Boolean formula that I just showed you?

Well, what we could do is turn this into a Boolean formula

with a huge number of variables,

but you will see that the number of variables is still polynomial.

So what are my variables going to be?

I'm going to have one variable

for each of those black boxes here

and also one variable for each of these here,

and so on, and so on, and so on.

I'm going to have

one variable for all of the possibilities

where I could be in my program code,

and again here I'm going to do the same thing as I did here on the left side.

I will have one Boolean variable

for each of those possibilities,

and what one of those Boolean variables means is

basicallyor what I want it to mean is

if it's set to true,

it tells me that

a memory cell contains that value,

so if this variable here is set to true,

I want that memory cell up here to contain the value 0.

If it's set to 1, I want this one here to contain the value 1.

If it's set to 2, I want this one here to have the value 2, and so on.

And now you see why the Boolean formula that I just showed you

where you can force just exactly one single variable to be true

is useful in this case,

because if I put all of these variables here

into such a Boolean formula,

I would have a Boolean formula that can be satisfied

if and only if

exactly one of those variables here is true,

so it tells me

uniquely what goes into this memory cell here

as long as it's satisfied,

and the same thing over here, and over here, and over here.

And now

if I write this Boolean formula for this memory cell here,

I write it for this memory cell here, here of course also,

and so on,

and if I combine all of those Boolean formulas,

so I have a Boolean formula here,

I have a Boolean formula here,

I have one here,

from this column,

from this column,

from this column, and so on.

So I have Boolean formula,

and then I do an and,

and I have the next Boolean formula, and I have an and,

and I have the next Boolean formula,

and I continue doing this, and I will also do this here for the program.

And of course, I will get a very, very, very large Boolean formula.