I was wondering if for a NP-hard optimization problem, I only want to find its local minimizer, is it still NP-hard or NP-hard is only true when trying to find a global minimizer?
3
-
3$\begingroup$ I find this question much too vague and vote to close until it's phrased more carefully . First, not all problems are optimization problems, hence, asking for a "local minimizer of an NP-hard problem" does not make sense. Second, "NP-hardness" is not a property of some problem, but of some problem class. Third, it may well be that for some problem class global minimizers are hard to find while local minimizers aren't, but for some other problem class its different. Or are you looking for a specific result telling that "if global minimizers are NP-hard to find, then local minimizers too"? $\endgroup$– DirkCommented Jan 26, 2016 at 7:48
-
$\begingroup$ Yest that's what I mean "if global minimizers are NP-hard to find, then local minimizers too" $\endgroup$– sjtupuzhaoCommented Jan 26, 2016 at 9:32
-
$\begingroup$ Now you have two contradicting answers that answer slightly but crucially different interpretations of your question. $\endgroup$– DirkCommented Jan 26, 2016 at 10:23
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Yes, even verifying local optimality is hard.
Check out this famous paper of Murty and Kabadi, which considers NP-completeness in nonlinear programming, and in particular discusses hardness of local optimization too.
$\begingroup$
$\endgroup$
Not really, it depends on the problem and the definition of neighborhood.
Consider a simple problem of TSP and define a neighborhood by 2-swaps. A greedy algorithm that consider all two swaps and proceed with the an improving 2-swap is guaranteed to stop at a local minimum. In practice this does not take long until the code get stuck.
