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

<p>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 <a href="http://link.springer.com/article/10.1007%2FBF00120662">http://link.springer.com/article/10.1007%2FBF00120662</a>. </p>

<p>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.</p>

CC BY-SA 3.0
2013-11-19T18:03:19.513Z
2013-11-19T18:03:19.513Z
Thang Dinh
<p>If this is known, can someone point me to a proof?</p>

<p>Edit:</p>

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

<p>minimize $\frac{1}{2} x^T Q x + c^T x$</p>

<p>s.t. $Ax \leq b$</p>

<p>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?</p>

CC BY-SA 3.0
2013-11-15T18:55:19.873Z
For better clarity, give a formal definition of the decision problem  in the question (and a brief definition of QP).
Marzio De Biasi
CC BY-SA 3.0
2013-11-15T19:49:55.240Z
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.
George
CC BY-SA 3.0
2013-11-15T20:37:54.727Z
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).
Daishisan
CC BY-SA 3.0
2013-11-15T20:51:50.480Z
Just a note: I think that [QP is in NP](http://www.sciencedirect.com/science/article/pii/002001909090100C) (so it is NP-complete).
Marzio De Biasi
CC BY-SA 3.0
2013-11-15T23:00:53.473Z
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 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 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.
Thang Dinh
CC BY-SA 3.0
2013-11-18T21:48:25.553Z
@ThangDinh makes a good point -- just add a dummy variable to an arbitrary QP. I suggest you turn this into an answer.
Austin Buchanan
<np-hardness><optimization>
Is it NP-Complete to determine if a quadratic program (QP) has multiple solutions?
Daishisan
# Is it NP-Complete to determine if a quadratic program (QP) has multiple solutions?

(Asked by: username_0 on 2013-11-15)

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?

**Tags:** np-hardness, optimization
> **Comments:**
> **username_1**: For better clarity, give a formal definition of the decision problem  in the question (and a brief definition of QP).  
> **username_2**: 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.  
> **username_0**: 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).  
> **username_1**: Just a note: I think that [QP is in NP](http://www.sciencedirect.com/science/article/pii/002001909090100C) (so it is NP-complete).  
> **username_3**: 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 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 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.  
> **username_4**: @ThangDinh makes a good point -- just add a dummy variable to an arbitrary QP. I suggest you turn this into an answer.  

---

## 1 answers

### Answer by username_3 on 2013-11-19. Score: 7 | Accepted answer

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


---

