[Crossposted](https://math.stackexchange.com/q/4651807/339790) on Mathematics SE




---


I've seen in many optimisation papers the statement that general non-convex optimisation problem is NP-hard. If we assume that non-convex optimisation is in NP class, it can be shown, as I remember, that some NP-complete problems can be relaxed to corresponding continuous non-convex optimisation problems, which makes general non-convex optimisation problem NP-complete. But we assumed that it is in NP class, which is not obvious for me — indeed, it would mean that solution of multi-extremum problem can be verified in polynomial time. But it seems to be too strong and even practically important statement, which makes me sad that I do not know this fact (honestly, some important problems would be simpler that we think if it holds). In short — can one show that solution of non-convex optimisation problem can be verified in polynomial time, or it is in general more complicated problem than any in NP?



Is non-convex optimisation really in NP class?
As noted in a [comment by Emil Jeřábek](https://mathoverflow.net/questions/442071/is-non-convex-optimisation-really-in-np-class#comment1140811_442071), $\mathsf{NP}$ is a class of decision problems, so on the face of it, an optimization problem cannot be in $\mathsf{NP}$ for the rather trivial reason that it is the wrong type of thing. Nevertheless, people often do talk about $\mathsf{NP}$-complete optimization problems; what they mean is that the *decision version* of the optimization problem is $\mathsf{NP}$-complete:



> 
> $(\*)$ Given an instance of the problem and a number $k$, does there exist a solution with cost at most $k$?
> 
> 
> 


For most problems, the $(\*)$ is *polynomially equivalent* to the problem of computing the optimal cost. Namely, if you can solve $(\*)$ in polynomial time, then you can compute the optimal cost by performing a binary search on the value of $k$. Furthermore, for most problems, $(\*)$ is almost trivially in $\mathsf{NP}$; to confirm a "yes" answer, someone can provide a solution with cost $\le k$, and you can compute the cost and confirm that the cost is indeed $\le k$. Convexity or non-convexity does not have much to do with it.


There are, however, some objections that you can raise. The recipe in the preceding paragraph only tells you how to compute the optimal *cost* (if you know how to solve the decision version), and does not tell you how to compute an optimal *solution*. This objection can be met in the case of problems that are *self-reducible*. I won't define self-reducibility formally, but for example, maybe your variables are all 0-1 variables, and if you set one of the variables equal to 0 or 1, what you get is another (slightly smaller) instance of the same type of problem. In that case, once you have the optimal cost $k$, you can compute a solution by choosing some variable, setting it to 0 (say), and asking whether the resulting smaller problem admits a solution with cost $\le k$. If so, then permanently set it to 0; otherwise, permanently set it to 1. Either way, you can then proceed to the next variable, and set the values of all the variables one by one. Again, convexity or non-convexity has little to do with it.


You could also object that being "polynomially equivalent" in the above sense is too coarse an equivalence relation. I referred to $(\*)$ as **the** decision version, but what about this?



> 
> $(\dagger)$ Given an instance of the problem and a number $k$, is the optimum cost **exactly equal to** $k$?
> 
> 
> 


Maybe in your opinion, it is $(\dagger)$ and not $(\*)$ that should be called **the** decision version of the problem. (This seems to be what you're getting at with your question about the optimum solution being verifiable in polynomial time.) While $(\dagger)$ and $(\*)$ are polynomially equivalent in the sense that if you can solve either one in polynomial time then you can solve the other in polynomial time, it does not immediately follow that $(\dagger)$ is in $\mathsf{NP}$ even if $(\*)$ is in $\mathsf{NP}$. And in fact, for many optimization problems, $(\dagger)$ is in [$\mathsf{DP}$](https://complexityzoo.net/Complexity_Zoo:D#dp) but not necessarily in $\mathsf{NP}$. So in this sense, you can question whether it is really appropriate to say that an optimization problem is in $\mathsf{NP}$ just because $(\*)$ is in $\mathsf{NP}$. However, once again, note that this subtlety really has nothing to do with convexity versus non-convexity.


