Math's question (complexity theory)

[Colonel Olrik]

Hello Math experts, I need you. I'm having a slight disagreement with my second supervisor over part of the second chapter of my PhD thesis. Although my thesis is application oriented, since I'm using approximate algorithms for optimization I wrote a section about problem complexity, P and NP, NP-hard and NP-complete. The disagreement lies in the following paragraphs of my thesis:

The theory of NP-completeness formalizes the distinction between easy and hard to solve problems. In general, the theory concerns the decision version of combinatorial problems. The generality of the conclusions drawn in the theory is not in any way limited, since the optimization version of a problem is never easier to solve than the decision version. Therefore, if the optimization version of a problem can be solved efficiently, then the same must be true for the decision version.

The class of NP–complete problems is a subclass of the class NP. The class NP contains
decision problems that can be answered by “yes” or “no”. This means that for each problem in
NP there is for a “yes”-answer a solution, T, that can be used to check the correctness of the
yes-answer in polynomial time. For problems in the class NP it is only necessary that a solution can be checked in polynomial
time, not that the solution can be found in polynomial time.

Based on my references, I say that the NP and NP-complete definitions only strictly apply to decision problems. Furthemore, I say that:

Only a combinatorial decision problem can be NP or NP-complete. Combinatorial optimization
problems do not belong to the NP or NP-class. However, optimization problems
can belong to the class NP-hard. The NP-hard class is the class of problems which are at
least as hard as NP-complete problems, but not necessarily element of NP. Therefore, all
NP-complete problems are also NP-hard.

My supervisor argues that the definitions of NP and NP-complete also apply to combinatorial problems. In fact, he goes a step further and said that there's no actual difference between search, decision and optimization besides semantics. However, he didn't have any references supporting his point of view and told me (when I showed him my research) that I should study and look in wikipedia (!). Anyway, like me he's not a mathematician or an expert in this field.

So, my question is if you can enlighten me about this subject, and who's right, and if you can maybe give me some solid references I can use. I've found some publications that seem to defend his view, but there are the several I already had that say exactly what I wrote. I don't have much time to spend on this (and don't want anymore) and I'm confused

Thanks in advance.

[Kuroneko]

I'm very far from an expert in complexity theory, so if you're writing a thesis relating to it, you most likely already have better sources than any I could competently vouch for. So take this with a grain of salt and check with your own sources. However, I think I understand why you have seemingly contradictory statements on this issue.

The classes of NP, NP-complete, etc. are defined for decision problems. However, there is also a corresponding class NPO of optimization problems. Your supervisor has a point in that if one is concerned more with applications, the distinction between NP and NPO may stop seeming to be of much import, and one might start talking about optimization problems being "NP" where one 'really' means "NPO". It isn't really a big deal, since it should be quite clear from context which is meant.

So although you're technically right, the easiest way to deal with the dispute is probably just to acknowledge your supervisor's criticism by making that distinction in at least a footnote if not the main body. You can find a rigorous definition easily if you wish, but the main idea is pretty simple: for any optimization problem, you're ranking the solutions to some corresponding problem; if the solution set is polynomial-bounded in instance size of the optimization problem, solutions can recognized as such in polynomial time, and the measure that ranks them is itself polynomial-time computable, then the optimization problem is NPO.

[Colonel Olrik]

(modestly bows to Kuroneko)

Thanks!! That helped a lot as you put me in the right direction. I changed the text to the following (nevermind the English, it may need refinement):

The theory of NP-completeness formalizes the distinction between easy (class P) and hard to
solve problems (classes NP to EXPSPACE). Strictly speaking, the theory concerns the decision
version of combinatorial problems (problems that can be answered by “yes” or “no”) [10], [8].
For problems in the class NP it is only necessary that a solution can be checked in polynomial
time, not that the solution can be found in polynomial time. Closely related to the NP class is
the class NPO of optimization problems. For any optimization problem, solutions are ranked
to some corresponding problem. If the solution set is polynomial-bounded in instance size of the
optimization problem, solutions can recognized as such in polynomial time, and the function that
ranks them is itself polynomial-time computable, then the optimization problem is NPO [5].

From the definitions of NP and NPO, it follows that the optimization version of a problem is
never easier to solve than the associated decision version. Therefore, if the optimization version
of a problem can be solved efficiently, then the same must be true for the decision version [19].
The distinction between NP and NPO lies only in the existence, in the NPO classification,
of a (polynomial-time computable) cost function. Due to the similarities in the concepts and for
simplicity reasons, it is usual in application oriented research to talk about optimization problems
being NP where one “really” means NPO, since it should be easy to determine by the context
to which type of problems, decision or optimization, the classification is applied. This is the
approach followed in this thesis.