Edit: Never mind. It’s only NP-complete if you’re just trying to figure out if it’s possible. Optimizing is NP-hard.
Once you actually finish the optimisation problem shouldn’t you then have the best possible solution? That is, either your result fits or it doesn’t. How can finding the best possible solution be less difficult than just finding out whether it is possible to have a solution?
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.
Once you actually finish the optimisation problem shouldn’t you then have the best possible solution? That is, either your result fits or it doesn’t. How can finding the best possible solution be less difficult than just finding out whether it is possible to have a solution?
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”.