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.
The knapsack is NP-complete. It’s technically also NP-hard, but NP-complete is more specific.
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.
NP-hard is “at least as hard as NP-complete”.
A curse on the ambiguity inherent in English language.
The only time that it is NP-complete is if you’re just trying to figure out if it’s possible.
It’s merely NP-complete if you’re just trying to figure out if it’s possible.
This makes much more sense now that I’ve spotted the intended meaning.