28
7
I am slightly confused by some terminology I have encountered regarding the complexity of optimization problems. In an algorithms class, I had the large parsimony problem described as NP-complete. However, I am not exactly sure what the term NP-complete means in the context of an optimization problem. Does this just mean that the corresponding decision problem is NP-complete? And does that mean that the optimization problem may in fact be harder (perhaps outside of NP)?
In particular, I am concerned about the fact that while an NP-complete decision problem is polynomial time verifiable, a solution to a corresponding optimization problem does not appear to be polynomial time verifiable. Does that mean that the problem is not really in NP, or is polynomial time verifiability only a characteristic of NP decision problems?
your link to the large parsimony problem on wikipedia defines it only in general but not mathematical terms. there are multiple ways to mathematically describe the same problem. also suspect that maybe what the professor meant was NP Hard which is quite different, it only proves its at least as hard as all NP problems but could be harder. NP Complete also assures the problem is not harder than any other NP problems (wrt PTime reductions). – vzn – 2012-09-23T14:50:47.737
3
check this question
– Ran G. – 2012-04-02T04:47:50.7501
Also this question: Optimization version of decision problems.
– Kaveh – 2012-04-02T05:10:07.5931@RanG., I am not sure if this is an exact duplicate. – Kaveh – 2012-04-02T05:11:04.050
@Kaveh you're right, but the great answer of uli fully answers this question. – Ran G. – 2012-04-02T05:16:20.293
@RanG., there can be more than one great answers. :) – Kaveh – 2012-04-02T05:17:47.690