wedrifid comments on Balancing Costs to Ourselves with Benefits to Others - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Loading…
Subscribe to RSS Feed
Powered by Reddit
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (43)
NP-hard is harder than NP-complete. Finding the best possible solution is the harder one.
This makes me wonder why you said "It's technically also NP-hard, but NP-complete is more specific". That is a statement that I took to infer that the NP-complete ones were more difficult.
NP-hard = harder or equal to, not harder, than NP-complete. He was likely just demonstrating mastery of the subject :)
First, suppose your problem is NP-hard. This means "at least as hard as one of the NP-complete problems, e.g. 3SAT", in that if you have a poly-time solution to your problem, it can be used to make a poly-time solution to the NP-complete problem.
Now, becoming more specific: what if a P-time solution to one of the NP-complete problems would yield a P-time solution to your problem? Then your problem joins the class of NP-complete problems, which are all P-time reducible to one another.
NP-hard is "at least as hard as NP-complete".