$)$Here are some statements about computational complexity. They may be correct, incorrect,

misleading or meaningless. In some cases the truth or otherwise of the statement might not be

known, either in the sense of it not having been covered in the course or by the answer not

being known by anybody anywhere. For each statement comment on its validity and in cases

where that is both necessary and straightforward produce an adjusted version of the

observation that is properly valid. You are not expected to include proofs to support your

claims.

$($a$)$ Problems that are not NP$-$complete are easy to solve. $(2$ points$)$

$($b$)$ Problems that are NP$-$complete will never be solved in reasonable amounts of time even

though computers continue to get faster and faster. $(2$ points$)$

$($c$)$ To test a number N to see whether it is prime you just have to do a testdivision by each of

the numbers from $2$ to N $1,$ and since there are only N $2$ of these and division can be done in

time O$($n $2)$ this is polynomial time. Thus primality testing is in the class P$.(2$ points$)$

$($d$)$ There is a polynomial$-$time reduction from the k$-$clique problem to $3-$SAT. $(2$ points$)$

$($e$)$ There is a polynomial$-$time reduction from $3-$SAT to the k$-$clique problem. $(2$ points$)$

$($f $)$ There have been proposals that biological computers based on DNA might use the massive

parallelism of their biochemical activity to solve NP problems rapidly. If such systems could be

made to work reliably this would solve the theoretical challenge posed by the concept of NPcompleteness. $(2$ points$)$