Oh ok, I understand what you mean.
reply(By the way, I think you mean NP-complete, not NP-hard. The Halting Problem is NP-hard.)
The halting problem is NP hard, technically speaking, but it's much harder than that - it's uncomputable. I don't think it's common to refer to it as NP-hard because it's confusing.
replyThanks for the correction! I updated my answer to fix that :)
reply"Any NP complete problem can be changed into 3SAT in polynomial time" - if I remember correctly, turning an NP-complete problem into 3SAT is not part of the problem statement - it just means that when working with NP-complete problems, they are always translated to 3SAT first, and whenever someone is trying to prove something they are working against 3SAT.
replyoh that actually helps a lot. I was tying myself in knots trying to think it through.
reply