to reduce problem A to problem C, we just compose the corresponding function.

So, assume that we have an instance IA of the problem A, and

we need to get an instance of a problem C.

For this, we first apply the algorithm fAB to

the instance IA, this gives us an instance of the problem B.

We then apply the algorithm fBC to the resulting instance of the problem B.

This gives us an instance of the problem C.

The important thing to note here is

that the resulting composed algorithm has polynomial time.

To see this note that, assume for

example that the running time of the algorithm fAB is for

example P(n) and its running time is n cubed for example.

And the running time of the algorithm f sub AB is q of n and it is n to the 5.

Then the running time of the composed algorithm is p(q(n).

This is p(n) to the 5, and this is in turn

n to the 5 cubed, which gives us n to the 15.

Namely, when you compose two polynomial functions,

you get also polynomial function.

Which justifies that the running time of this algorithm is also polynomial.

To get an algorithm which transforms the solution to C back through the solution

of A, you just apply the combination of the correspondent to each algorithm.

Namely, when you get a solution S sub C for

the problem C, you first apply the algorithm hBC.

This gives you a solution back to the problem B.

Then you apply the algorithm h of AB to

transform it back to a solution of the problem A.

Pictorially, this composition of reductions means the following.

Whenever we have these two pair of edges in our graph of

all problems of the class NP.

We also have the following edge, right?

So once again if A reduces to B and B reduces to C, then A reduces to C.

In other words, if there is an edge from A to B and from B to C,

then there is an edge from A to C.

Yeah, so simple.

This allows us to prove NP-completeness as follows.

If we know that A reduces to B, and we know that A is NP-complete,

then so is the problem B, then B is also NP-complete.

Let me prove this pictorially, so this is, again,

our graph, we have two problems, A and B.

And we know that A reduces to B.

We also know that A is NP-complete.

Meaning that A attracts all other problems.

In other words, there is an edge from any other problem to A.

Now, since there is an edge from any other problem to A, and that at the same time,

there is an edge from A to B, through the composition of reductions,

we know that there is an edge from any other problem to B, right.

So this is the picture that we have.

B also attracts all as a problems, so by definition it is also NP-complete.

Our plan for the rest of this module is the following.

We will first show that the independent set problem

can be reduced to a vortex cover problem.

We will then show that the 3-satisfiability problem

reduces to independent set problem.

We will then show that satisfiability problems,

a general version of satisfiability problems,

reduces to its special case, namely to this re-satisfiability problem.

And finally we will show that all other search problems reduce to SAT,

in particular the 3 problems shown here above the satisfiability problem.