Remix clone Hacker News

> 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?

▲

Khoth 6 days ago | parent | next [-]

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)

▲

redleader55 6 days ago | parent | prev [-]

This [1] diagram from Wikipedia represents you are saying in a visual way. NP-hard and NP-complete are defined as basically an equivalence class modulo an algorithm in P which transforms from one problem to the other. In more human terms both NP-hard and NP-complete are reducible with a polynomial algorithm to another problem from their respective class, making them at least as hard.

The difference between the two classes, again in human terms, is that NP-complete problems are decision problems "Does X have property Y?", while NP-hard problems can include more types - search problems, optimization, etc, making the class NP-hard strictly larger than NP-complete in set terms.

The statement in the article means that NP-hard problems require solving a NP-complete problem plus a P problem - hence being at least as hard.

[1] https://en.m.wikipedia.org/wiki/File:P_np_np-complete_np-har...

▲

edanm 5 days ago | parent | next [-]

I don't believe this is accurate.

The difference between NP-Hard and NP-Complete is that NP-Complete problems are both NP-Hard, and in NP. As opposed to NP-Hard problems that are not NP-Complete, meaning they are not themselves in NP.

▲

zahlman 5 days ago | parent | prev [-]

If NP-hard isn't even a subset of NP, why is it called "NP-hard"?

	▲	suzumer 5 days ago \| parent \| next [-]
		Because a language being NP-hard implies it is at least as hard as the hardest NP problems. For any language that is NP-hard, if one had a turing machine that decided the language, one could construct a polynomial time transformation of any language in NP to the NP-hard language to decide it using the NP-hard turing machine.
	▲	sfink 5 days ago \| parent \| prev \| next [-]
		Membership in NP is a statement about how easy a problem is (specifically, that you can verify an answer in no worse than polynomial time). NP-hard is about how hard a problem is (at a minimum). I wonder if there would be less confusion over this if NP had been called "NP-easy" in the first place. But Wikipedia says that by now that term has already been taken. P is "very easy": you can solve these in polynomial time. NP is "easy": you can verify a solution in polynomial time. Are there any problems you can verify but not solve in polynomial time? Nobody knows! (But ~everyone thinks so.) NP-hard is "hard": it takes polynomial time or more to even verify these.
	▲	Sharlin 5 days ago \| parent \| prev [-]
		Because naming things is one of the two difficult problems in computer science.