
Title:
0801 Algorithms To Boolean Formulae

Description:

So how can we take an algorithm and put that into a Boolean formula?

Well, that's where Cook and Levin had another ingenious idea,

because they said you can look at an algorithm

running on a RAM as a series of snapshots,

and what I mean by this is the following:

So assume you have an algorithm on a

nondeterministic RAM that runs in polynomial time,

so you have a point in time T equals 0, that's when your algorithm starts out,

then you have T equals 1, T equals 2, so those are the time steps here.

And the final time step is going to be some polynomial of N.

That is clear because we're looking at an algorithm

that solves a problem that lies in NP,

So that means it only takes polynomial time on a nondeterministic RAM at least.

Now if you look at what happens on the RAM in each time step,

I can basically draw you the following picture.

If you recall from unit one what the RAM looks like,

the RAM has only a few components.

The RAM has a readonly memory,

the RAM has a program or the algorithm running,

so this algorithm here is basically the program running,

and just as I would write the algorithm line by line by line,

I can also write it in this way,

so this here would be the first line of code,

then this would be the second line of code, and so on.

And finally, the RAM had a reading and writing memory,

so we had some memory cells here holding the variables,

and those variables, of course, are changed by the program

depending on what's here in the input.

And now comes the neat part that Cook and Levin observed,

because what they observed is

that when you look at an algorithm working on the RAM,

then you can depict that as a number of these snapshots,

so if you say, add T equals 0,

these are the contents of the readonly memory.

This is, actually we need other information,

we also needs to know where the program is at,

but you can basically say, this is the input here,

this is the program, and this is the line of the program that we're executing right now,

and this here is the contents of the read/write memory.

In the beginning this will be empty,

but as the algorithm works, it will also put some content in here,

and then, of course, the program moves on.

It can also jump back and forth here,

and of course, we will have more and more content in the memory,

and at a certain point in time the program will say, I'm done,

and it will hopefully have a certain output here.

But since we're working with decision problems,

actually it's only interesting to us if the program says, yes or no at the end.

So for decision problems we don't even really care about what's in here,

we would care about that if we were solving the optimization problem

or want additional information,

but actually for a decision problem,

it would just be important for us to know

at which line of code the algorithm finishes.

If it finishes at a return statement that will return yes to us

or a return statement that will return no to us.

Now let's have a closer look at those snapshots,

and we'll actually do that as a quiz.

So this here is one snapshot.

I would like you to tell me what we can say about a single snapshot

and also about all of these snapshots here.

So there are 3 statements,

each of which I would like you to check this box if you think they are true

and otherwise leave it blank.

So the first claim you could make is that each snapshot has size polynomial in N,

and N is the size of the input as always.

Secondly, you could claim that there can be

an exponential number of snapshots if we look at all of the time steps.

And finally, one claim that I would like you to check out as well is

all snapshots, if taken together,

so this whole part here,

have polynomial size,

and by polynomial size, I again mean that it's some

polynomial of the input size that we're always using.

You should keep in mind that the algorithm

that we're looking at is an algorithm for a problem in NP,

and it runs on a nondeterministic RAM.