# wedrifid comments on Balancing Costs to Ourselves with Benefits to Others - Less Wrong Discussion

4 22 June 2012 10:31PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Sort By: Best

Comment author: 23 June 2012 03:20:14AM -1 points [-]

NP-hard is harder than NP-complete. Finding the best possible solution is the harder one.

Comment author: 23 June 2012 03:36:26AM 2 points [-]

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.

Comment author: 30 June 2012 10:50:14PM 0 points [-]

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.

Comment author: 23 June 2012 06:26:39AM 0 points [-]

NP-hard is "at least as hard as NP-complete".