Steiner Minimal Trees and NP
What is the difference between the following Steiner trees: (Non-)Metric Steiner Minimal Tree, Euclidean Steiner Minimal Tree, Graph Steiner Minimal Tree, etc? Which of these are NP-complete and which are NP-hard? Some of the online resources I found suggest that Steiner trees are NP-hard, and others suggest it's NP-complete, but I believe they are referring to different versions/variants of the problem.
Update: nevermind, I've figured it out. The decision problem of SMT is NP-complete because, given a Steiner tree and an integer k, it is easy to verify in polynomial time whether the cost of the tree is less than or equal to k. But the optimization problem of SMT does not have a polynomial time verifier (we can still find the cost of the tree, but we cannot verify that it is the optimal solution), so it's NP-hard.
I was confused by NP-completeness and NP-hardnesses of problems a lot, especially since it sometimes looks like they are used interchangeably.
The catch is very simple. NP-complete is a subclass of NP which is the class of polynomial time verifiable decision problems. So only decision problems can be NP-complete, and an optimization problem is never NP-complete.
NP-Hard means just any problem that's at least as hard as NP-complete, including both decision and optimization problems. Therefore all NP-Complete decision problems are also NP-Hard. If a decision problem is NP-Complete the optimization version is NP-Hard because if you have a solution to the optimization, you can also use it to answer the decision problem. However the converse is not necessarily true.
So technically per definition, even if the optimization problem had a polynomial time verifier it would still not be NP-complete.
链接地址: http://www.djcxy.com/p/40002.html下一篇: 斯坦纳最小的树和NP