# Does $\mathsf{P} = \mathsf{NP}$ imply $\mathsf{PO} = \mathsf{NPO}$?

The class $$\mathsf{NPO}$$ is defined as optimization problems such that the corresponding decision problems defined with a threshold are in $$\mathsf{NP}$$.

Let $$A$$ be an optimization problem and $$B$$ a decision problem associated to $$A$$ with a threshold. If we can solve $$B$$ in polynomial time, is it the same for $$A$$?

I have the answer for some problems, but I am not sure it can be generalized. For example, the optimization TSP could be solved in polynomial time if we can solve the decision TSP in polynomial time:

• one can find the weight of a minimal tour, using dichotomic search;
• for each edge, remove it and check if there is still a minimal weight tour. If that's not the case, remove it, otherwise, keep it.

Another similar question (but I am not sure it is equivalent or not) is the one in the title of the post: does $$\mathsf{P} = \mathsf{NP}$$ imply $$\mathsf{PO} = \mathsf{NPO}$$?

• $NPO\subset FNP$ and $P=NP\iff FP=FNP$. Commented Dec 18, 2023 at 11:40
• @rus9384 you can create an answer with this property, and I would like it very much if you have references to those two properties! Commented Dec 18, 2023 at 14:47

Every optimization problem is asking about what's the value of a certain parameter closest to some target that's achievable under certain conditions. For example:

What's the largest clique in the given graph?

Here the clique size is the parameter, the target is $$\infty$$ and the description of the graph is the set of conditions.

The answer, quite clearly, can require more than one bit of information. Such a problem is called a function problem. Not every function problem is an optimization problem. For example, a function problem can be asking what is the satisfying assignment for the given boolean formula, rather than asking what's the maximum amount of clauses that can be satisfied at once. This establishes that optimization problems are a subclass of function problems.

When talking about $$\mathsf{NP}$$-optimization problems specifically, we can state that $$\mathsf{NPO}\subset\mathsf{FNP}$$. The latter being the class of function problems solvable by non-deterministic Turing machines that can run for polynomially bounded time. Its deterministic counterpart is called $$\mathsf{FP}$$.

The reasoning in your post is correct and from that it follows that $$\mathsf{P=NP\iff FP=FNP}$$. The property of the $$\mathsf{NP}$$-complete problems you are using is called self-reducibility.

As for $$\mathsf{PO}$$ and $$\mathsf{NPO}$$ specifically, it also follows that $$\mathsf{PO\subset FP}$$. Therefore, given $$\mathsf{FP=FNP}$$ it would follow that $$\mathsf{NPO\subset FNP\cap NPO=FP\cap NPO}$$. And it only makes sense to define $$\mathsf{PO}$$ in such a way that it is equivalent to $$\mathsf{FP\cap NPO}$$.

• I am sorry, but it is unclear for me that $\mathsf{NPO}\subseteq \mathsf{FNP}$. If I understand correctly, $\mathsf{FNP}$ is roughly the class of search problems where you search a certificate for a $\mathsf{NP}$ problem. However, $\mathsf{NPO}$ would be the class of optimization problems where you search "the best" certificate, and then that could be more difficult than finding any certificate. Commented Dec 20, 2023 at 19:09
• $\mathsf{FNP}$ is a class of problems solvable by a non-deterministic polynomial time machine that can return "long" answers. I.e. not just 0 or 1. Trivially, a long answer suffices to answer an optimization problem. Commented Dec 20, 2023 at 19:33
• "Trivially, a long answer suffices to answer an optimization problem." > that's not so trivial for me: you can convince me that a graph contains a clique of size more than $k$ by finding one, but it will be hard to convince me that the one you found is the biggest one in poly-time. Commented Dec 20, 2023 at 20:02
• It does not have to be convincing, that's not the part of the definition of NPO. NPO would be contained in $\mathsf{FP^{NP}}$, but if $\mathsf{P=NP}$ it becomes $\mathsf{FP^P=FP}$ which shows the desired property. Commented Dec 20, 2023 at 20:04
• You wrote $\mathsf{NPO}\subseteq \mathsf{FNP}$ and now $\mathsf{NPO}\subseteq \mathsf{FP}^{\mathsf{NP}}$. Could you please give references for those results? Commented Dec 20, 2023 at 20:09