0
$\begingroup$

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?

This question has been crossposted on MathOverflow.

$\endgroup$

1 Answer 1

1
$\begingroup$

NP problems are decision problems, so an optimization problem would need to be restated as a decision problem. Instead of asking what value of $x$ minimizes a function, you would ask if there is a value of $x$ where $f(x)$ is less than some $N$. The problem is in NP as long as $f(x)$ can be evaluated in time polynomial to the size of any input $x$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .