Exercici 8 (Tasca 7).
(NP,
NP-completeness)
\mathsf{NP} i \mathtt{HALT}
Demostreu que \mathtt{HALT} és \mathsf{NP}-difícil. És també \mathsf{NP}-complet?
Nota
Recordeu que \mathtt{HALT}=\{\langle x,y \rangle \mid M_x(y)\!\downarrow\}\ , on M_x és la màquina de Turing amb nombre de Gödel x i el símbol \downarrow indica que la màquina finalitza.