$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$-(10\%)$ Determine whether the following statements are correct or not and justify your answers.

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

the time complexity of each iteration.

$($b$)(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.

$($c$)(2\%)$ If $P_1$ and $P_2$ both are NP$-$complete problems, then we can conclude that $P_{1}prop{P}_2$ and

$P_{2}prop{P}_1.$

$($d$)(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$-$complete problem.

$($e$)(2\%)$ According to the NP$-$completeness theory, if any NP$-$complete problem can be

solved in polynomial time, then $NP=P.$

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.