The non-deterministic version and the complement of the non-deterministic version.

So I'm...

You already have this diagram written out probably.

We have something like this. These inclusions here hold because if we are on deterministic machines,

we... a machine running with certain bound on space using exponentially more time like here and here.

About the co-versions of deterministic classes because if we can decide a problem and give the answer yes,

we can also give the answer no. So both classes are equal. P and co-P mean the same.

And the goal of this lecture is to show that some of these containments can...

we can add more and more containments between these classes, in particular,

non-deterministic classes corresponding to non-deterministic Turing machines with bounds on space.

We will add by the end inclusions here and the tools we will need for this are some of the results from Wednesday,

namely that the reachability problem on graph is in polynomial time. This is something, as I mentioned,

you already know from your courses on data structures and graph algorithms.

And we will also use the improved version on space of this result that says that reachability on a graph

can be solved in space square of a logarithmic for some constant.

So this says that for this, the standard algorithm needs linear space, but we saw that there is a way to

solve this problem with the square of a logarithmic in space. It's less efficient in time, but needs less resources.

This will be the tools we will use. And what we need to do essentially to

add these show containments here is a way for showing that given a problem that is in one class,

let's say a problem in nl, can be solved also in p, for instance.

And the way we will do that is taking a Turing machine that solves the problem with this restriction in space

and running it somehow in polynomial time. And we will like to use graph reachability somehow to do this.

The other tool we will need is the idea of a configuration of a Turing machine, which is something quite straightforward.

It's just a description of the current state of the Turing machine, the total state.

Think of a real computer running a program. The state of the machine will be the content of all the memory,

the content of the registers, the value of the instruction pointer, and that's more or less it.

If you know that, if you have that snapshot of the machine, you know precisely what would be the next instruction, etc.

That's in fact if you configure your Linux appropriately when you get a segmentation fault,

this snapshot of the content is dumped to your disk. It's called a core dump, it has all the content of your memory, registers, etc.

And the equivalent of the core dump of a Turing machine is called a configuration.

What we need to have in this case is what is the state, the current state of the Turing machine,

where the heads are positioned on each tape, what's the content of the tapes.

If we know all that, we know an exact state of the machine.

So now one little observation is that in principle for a given Turing machine there could be infinitely many configurations,

infinitely many snapshots in which it could be. Why infinitely many?

Well, because in each tape we could have strings of arbitrary length.

The machine could have written arbitrary unbounded amount of things on the work tapes.

But we are interested in Turing machines that run with some bound on the usage of the working tapes.

So we can exploit that and refer to configurations which are somehow bounded in space.

The working tapes are not larger than something,

and that will give us a finite set of relevant configurations for a given Turing machine and a given input.

Let's define this properly.

So we define the notion of a configuration where the strings in the working tapes is bounded in size.

That's the idea. So assume that we have a given Turing machine M,

and let's assume that the states are numbered.

Let's say state 1, 2, 3, state M for a large enough M. Let's say it has K working tapes.

Remember that we are assuming that the input tape is not writable,

and since we are working on decision problems, we don't have a write tape.

They are all working tapes. There's no write-only tape.

So for this situation, also assume we have a function f,