The halting problem is not NP-complete since it is not in NP.