
So our three problems are so closely related that either all of them lie here in NP but not in P

or all of them lie in P.

We don't know which one it is but it can't be the case that,

for example, we have just vertex cover in P and the other two problems here in NP.

And how did we show that in the last unit?

For clique and independent set, we showed that there was a polynomial time algorithm

that could take a graph that was an input to independent set

and transform that into a graph that we can use as an input for clique,

and once we have solved the clique problem on the transformed graph,

that same solution is also the best possible solution to independent set.

So we have a polynomial time algorithm, so the algorithm transforms the input of one problem,

say X, into an input of another problem, Y.

So, for example, we take independent set and transform that graph into an input for clique

and now you'll see one of the advantages of working with decision problems

because the third condition is rather easy to state because we can now simply say that

solving the problem Y on the transformed input yields the same answer

as solving the original problem on the original input.

So these three statements here are the same thing that you have seen in the last unit.

So, we took an input which was a graph to independent set

then transformed it into an input for clique and we found out that if we solve clique on that new input,

then we would get the same answer that we would've gotten

if we had solved independent set directly on the original input.

And of course we also saw that the transformation works in the other way,

so we could transform an input to clique into an input of independent set

and now for a vertex cover and independent set, it was even easier

because we didn't even have to transform the input, so basically the transformation was,

we could keep the input as it is, the only thing is if we're working with the decision problem,

of course, the answer will be a little bit different, so if we have a vertex cover of size k

for a graph with N vertices, then for independent set,

we must ask if we have an independent set of size nk.

But other than that, the transformation here is very easy.