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

$(2)(2\%)$ Given a set of cities, the traveling salesperson problem is to find a shortest round$-$

trip tour that visits each city exactly once and returns to the starting city. The traveling

salesperson problem is known to be an NP problem.

$($b$)(2\%)$ Not all NP problems can be reduced to the SAT problem.

$($c$)(2\%)$ By the Cook's theorem, if the SAT problem is not a $P$ problem, then $NPP.$

$($d$)(2\%)$ If a problem is shown to be NP$-$complete, then it means that we are not able to find

any polynomial time algorithm to solve this problem.

$($e$)(2\%)$ The difficulty degrees of any two NP$-$hard problems are equivalent.$(21\%)$ Determine whether the following statements are correct or not and justify your answers.

$($a$)(3\%)$ The time complexity of the whole prune and search process is not the same order as

the time of each iteration.

$($b$)(3\%)$ In the prune and search algorithm of the selection problem, the input elements are

divided into group of $5.$ But the algorithm dose not run in linear time if the input elements

are divided into groups of $7.$

$($c$)(3\%)$ The $\frac{0}{1}$ knapsack problem can be solved by a dynamic programming algorithm in

polynomial time.

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

polynomial 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\%)$ We can say that the traveling salesperson problem is an NP$-$complete problem.

$($g$)(3\%)$ If 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.$