3
$\begingroup$

If this is known, can someone point me to a proof?

Edit:

A QP is essentially a LP with a quadratic objective. That is, it looks like:

minimize $\frac{1}{2} x^T Q x + c^T x$

s.t. $Ax \leq b$

It's known that in general, solving a QP is NP-Hard. Is it NP-Complete to know if there are at least two different solutions to the QP?

$\endgroup$
  • 4
    $\begingroup$ For better clarity, give a formal definition of the decision problem in the question (and a brief definition of QP). $\endgroup$ – Marzio De Biasi Nov 15 '13 at 18:55
  • $\begingroup$ Assuming that your problem instance can be solved in polynomial time, I think you can check if there are more solutions in polynomial time. Find a solution X, then check for each variable whether there is another solution with a value different than the one in X (by adding one constraint). In other words, for each x_i, check whether there is a solution with the additional constraint that x_i > X_i or x_i < X_i (X_i is the value x_i takes in X). If there is another solution, at least one variable will have a different value. $\endgroup$ – George Nov 15 '13 at 19:49
  • 1
    $\begingroup$ George: It's NP-Hard to solve QPs in general so this won't work. Also, the constraints need to be non-strict inequalities (like in LPs). $\endgroup$ – Daishisan Nov 15 '13 at 20:37
  • 1
    $\begingroup$ Just a note: I think that QP is in NP (so it is NP-complete). $\endgroup$ – Marzio De Biasi Nov 15 '13 at 20:51
  • 1
    $\begingroup$ To determinine if a quadratic program (QP) has multiple solutions (so you have to answer "Yes" if the QP has more than one solutions, and "No" if it has one or no solution) can be shown to be NP-complete by modifying the proof on NP-completeness of QP here link.springer.com/article/10.1007%2FBF00120662. The proof uses a reduction from k-clique to a QP. Now, add a free variable to the QP, so that it has one solution iff it will have multiple ones. Thus, the answer to the problem if QP has multiple solutions or not gives the answer to the question if a graph has a clique of size k or not. $\endgroup$ – Thang Dinh Nov 15 '13 at 23:00
7
$\begingroup$

[Since I could not edit my comment, I repost it here as an answer]

To determine if a quadratic program (QP) has multiple solutions (so you have to answer "Yes" if the QP has more than one solutions, and "No" if it has one or no solution) can be shown to be NP-complete by modifying the proof on NP-completeness of QP here http://link.springer.com/article/10.1007%2FBF00120662.

The proof uses a reduction from k-clique to a QP. Now, add a free variable to the QP, so that it has one solution iff it have multiple ones. Thus, the answer to the problem if QP has multiple solutions or not gives the answer to the question if a graph has a clique of size k or not.

$\endgroup$

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.