If an optimization problem is mixed integer non-convex problem. The optimal solution by applying brute exhaustive search is infeasible to be applied in practice due to high complexity i.e. $O(N^K)$. Can we say that it's NP hard problem? If yes, can someone explain with more details.

  • 1
    $\begingroup$ You can't say it is NP-hard without giving a proof. $\endgroup$ – zdm Nov 22 '19 at 18:20
  • $\begingroup$ You can take the following mixed integer non-convex program. $\max xy$ subject to $x\geq0$, $y\in\{0,1\}$, and $xy\leq1$. The optimal solution is trivially $x=y=1$. $\endgroup$ – zdm Nov 22 '19 at 19:18
  • $\begingroup$ I don't know how can I use the above example to prove that the problem is NP-hard. However, my problem can be solved with brute force exhaustive search but it is impractical for larger values. Using continuous relaxation the problem is transformed to convex optimization problem. Then using Lagrange duality technique the optimal solution is obtained. $\endgroup$ – Fawad Khan Nov 27 '19 at 17:28
  • $\begingroup$ @zdm Can you please check the edited problem? $\endgroup$ – Fawad Khan Nov 27 '19 at 19:16

No, you can't infer NP-hardness from such an algorithm. Indeed, why should the existence of a slow algorithm mean that there can't be a fast algorithm?

For example, consider the problem of sorting $n$ integers. Suppose the first algorithm I give you is a one that tries all $n!$ permutations. Can we now safely conclude that this problem is somehow hard? Of course not and we know that there are many much faster polynomial-time algorithms for the problem.

  • $\begingroup$ Okay thank you so much for the explanation. $\endgroup$ – Fawad Khan Nov 27 '19 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.