Remix.run Logo
Khoth 6 days ago

NP-complete is indeed the intersection of NP-hard and NP.

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)