$1.$ Define the class P in terms of computational complexity. Explain why problems in P are

considered efficient. $(6$ marks$)$

$2.$ Describe the class NP and provide an example of a problem that belongs to NP but not

necessarily to P$.$ Explain why solving such problems is more challenging. $(5$ marks$)$

e

$42$

$7-8$

$5$

c

a b

d

$3.$ Define NP$-$complete $($NPC$)$ problems. Explain the significance of an NP$-$complete problem in

the context of computational complexity theory. $(6$ marks$)$

$4.$ Discuss the concept of polynomial$-$time reduction in the context of NP$-$completeness. How is

it used to establish the NP$-$completeness of a problem? $(5$ marks$)$