> NP-hard is the set all problems at least as hard as NP-complete
Im a bit confused by this. I thought NP-complete was the intersection of NP-hard and NP. Maybe this is stating the same?
replies(2):
If you can solve any NP-hard problem then you can solve any NP-complete problem (because you can convert any instance of an NP-complete problem to an NP-hard problem), so NP-hard problems are "at least as hard" as NP-complete problems.
(But an NP-hard problem might not be in NP, ie given a purported solution to an NP-hard problem you might not be able to verify it in polynomial time)