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.
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$.