$(18\%)$ Determine whether the following statements are correct or not and justify your answers.

$($a$)(3\%)$ If the running time of each iteration in a prune and search algorithm is $O(n^k),$

where $k$ is a positive constant, then the time complexity of this algorithm is $0(n^k).$

$($b$)(3\%)$ A dynamic programming algorithm can save its computation time by eliminating

some feasible solutions and also avoiding computing the same sub$-$problems repeatedly.

$($c$)(3\%)$ The Cook's theorem says that if the satisfiability problem is an NP problem, then

$P=NP.$

$($d$)(3\%)$ If a problem is NP$-$complete, then we can conclude that it cannot be solved by any

polynomial time algorithm in worst cases.

$($e$)(3\%)$ Suppose that a problem has been shown to be NP$-$complete. Then it means that we

need to take exponential time to solve this problem for all kinds of inputs.

$($f$)(3\%)$ If both problems $P_1$ and $P_2$ are known to be NP$-$hard, then we can conclude that

$P_{1}prop{P}_2$ and $P_{2}prop{P}_1.$