"(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 N

"(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.