$2.$ NP$-$Completeness $(24$ points$)$

Your professor at Hofstra comes to you one day claiming that they have finally solved

an NP$-$Complete problem. They tell you the following two statements.

$(1)$ The $3-$Coloring problem is solvable in worst case time $.$

$(2)$ In the worst case, there does not exist an algorithm to solve $3-$Coloring faster than

$.$

Assuming that your professor is correct, for each of the following statements below,

state whether the statement is true or false, and then write a few sentences to justify

your answer.

$($i$)$ All NP$-$Complete problems are solvable in polynomial time.

$($ii$)$ All problems in NP are solvable in polynomial time.

$($iii$)$ All NP$-$Hard problems are solvable in polynomial time.

O$($n$10)$

$\backslash$Omega $($n$8$

$)$

$($iv$)$ All NP$-$Complete problems are solvable in time.

$($v$)$ There exists no NP$-$complete problem that can be solved faster than in the

worst case.

$($vi$)$ P $=$ NP

O$($n$10)$

$\backslash$Omega