complete pr0blem also an NP
We can say that an NP-complete problem is one which is in NP and in NP-hard, but can we argue exclusively that a problem is NP-hard solely due to the fact that it is NP-complete.
Example: I reduce an NP-complete problem a to a problem b . Therefore, problem b is now proven to be NP-complete. Can I actually say that it is also NP-hard?
The definition of NP completeness is:
A problem Q is NP-complete if and only if Q is in NP and Q is NP-hard.
Therefore, yes, we can most definitely say that any NP-complete problem is NP-hard, by definition.
Note that you have a slight misstatement in your question:
Example: I reduce an NP-complete problem a to a problem b . Therefore, problem b is now proven to be NP-complete.
The above conclusion only holds if you've shown b to be in NP. If b is "harder" than NP, then it is not NP-complete. Note, however, that the reduction is enough to prove that b is NP-hard.
上一篇: 硬？
下一篇: 完成pr0blem也NP