Exercise 8 (Homework 7).
(NP,
NP-completeness)
\mathsf{NP} and \mathtt{HALT}
Show that \mathtt{HALT} is \mathsf{NP}-hard. Is it \mathsf{NP}-complete?
Note
Recall that \mathtt{HALT}=\{\langle x,y \rangle \mid M_x(y)\!\downarrow\}\ , where M_x is the Turing machine with Gödel number x and the \downarrow means that the machine terminates.