[AjayTripathy]

"(Recall that some NP-hard problems are not in NP; halting problem is one.)"

Actually, this quite clears it up for me, I was confusing being in NP with being NP hard.