Compare P$,$ NP$,$ NP$-$Hard and NP$-$Complete complexity classes of problems

diagrammatically.

Define a Clique in a graph. Define the optimisation version of the Clique

problem.

Define the decision version of the Clique problem.

Show that Clique is in NP$.$

Show that Clique is NP Hard by reducing it from Vertex Cover problem.

$"$If a problem $\text{'}$ X $\text{'}$ can be reduced from Clique in polynomial time then it is

NP$-$Complete". Comment.

Let S be an NP$-$complete problem, Q and R be two other problems not known to

be in NP$.$ Q is polynomial time reducible to S and S is polynomial$-$time reducible

to R$.($i$)$ Is Q NP$-$Hard? $($ii$)$ Is R NP$-$Hard? $($iii$)$ Is R NP$-$Complete? Justify your

claim in each case.