Explain why none of the following is NP-complete. a. The brute force TSP algorithm b. Merge sort c. The halting problem d. Hilbert’s 10th problem Solution. NP-completeness describes problems, not...

Explain why none of the following is NP-complete.

a. The brute force TSP algorithm

b. Merge sort

c. The halting problem

d. Hilbert’s 10th problem

Solution. NP-completeness describes problems, not specific algorithms for problems, so it is incorrect to describe (a) and (b) as NP-complete (apples and oranges are not NP-complete, either). The halting problem and Hilbert’s 10th problem are undecidable, so they are not in NP, and therefore not NP-complete.