So remember the 2 by 2 matrix that we drew a while ago.
We'll now have a closer look at this matrix as promised.
So what we just found out by the way is that this part here
anything you can do on a non-deterministic RAM in polynomial time
can also be one on a deterministic RAM in exponential time.
So any problem that is in this part down here would also be in this part up here.
But since we are mainly interested in polynomial time,
let's focus on the bottom part of this matrix for now.
You'll come back to the full matrix in later units when we talked about
exponential time complexity classes and remember that each of these squares
contains all of the problems that can be solved in polynomial time.
The left one on a deterministic RAM, and the right one on a non-deterministic RAM,
and now, we'll give these names.
So we'll call this complexity class here P, because those are all problems
that are solvable in polynomial time on a deterministic RAM.
And we'll call this here NP, because those are all problems solvable in polynomial time
on a non-deterministic RAM.
Of course, it wouldn't have been more consistent to call this one down here DP or something like that,
but this is the way we named it.
And now, what we also know is that any problem that can be solved in polynomial time
on a deterministic RAM can also be solved in polynomial time on a non-deterministic RAM.
We should probably rather redraw these black lines here like this because any problem
that is contained in P is automatically also contained in NP but of course not vice versa.
Otherwise, we would know that there is a polynomial time algorithm
for vertex cover and the two other problems.
So P contains all the problems that we know are easy.
So, for example, finding the shortest path between two points in the graph
or looking up an entry in the database multiplying two numbers and thousands of problems more.
So basically, any algorithm you'll have come across in an introductory algorithm scores
will fall into this category.
And again, there are some theoretical nitty-gritty regarding optimization and decision problems here,
but we can ignore that for the time being.
So let's do a little quiz to summarize what you know by now.
So given all you have learned, what can you say about P and NP?
So I would like you to check which of these statements are true.
The first statement is every problem in P is also contained in NP.
The second statement is that every problem in NP is also contained in P.
The third one is that P and NP are in fact equivalent.
The fourth one is that it seems like NP should contain more problems than P or be larger than P,
but we can't really say for sure.
The fifth one is that vertex cover, independent set, and clique are contained in P.
And the finally one is that those three problems are contained in NP.
So please check every statement which given what we know by now you should consider to be true.
