I am interested in a quadratic program of the form

$$ \min x^T Q x $$ $$s.t.$$ $$ Ax \leq b $$ where $x$ is a vector with $n$ entries, the size of the maximal entry in $Q, A$, and $b$ is $\varphi$, $A$ has $2^n$ rows, and $Q$ has $poly(n)$ rows.

Is it true that if there is a minimal solution to the program, then there is one of size that is polynomial in $n$ and $\phi$?


  • $\begingroup$ Do you know anything about $Q$? $\endgroup$ Commented Jan 4, 2015 at 15:48
  • $\begingroup$ In my case it is not positive semidefinite. What else can help? $\endgroup$
    – Guy
    Commented Jan 5, 2015 at 7:01

1 Answer 1


In Quadratic Programming is in NP, it is shown that a slight variant of this problem (QPL) is in NP. The question can be formulated as follows: does there exist a point $x \in \mathbb{R}^n$ such that $ Ax \leq b $ and $x^T Q x \leq K$, where $K$ is a rational number. In the section 2 of this paper, they prove that, when the minimum exists, then there is a minimum $x^*$ with a polynomial number of digits. Their proof is independent from $K$, so it directly applies to your formulation.

The claim that $x^*$ has a polynomial number of digits is not enough, since you want the solution to be polynomial in $\varphi$ and $n$.

In their proof, they define $x^*$ as a particular global minimum with the maximum number of active inequalities, and then, they construct a nonsingular system of linear equations and show that $x^*$ (or a projection of $x^*$) is its unique solution. Thanks to a theorem by Edmonds they conclude that $x^*$ has a polynomial number of digits.

Since the system has a unique solution, $x^*$ is also the solution to a subsystem consisting of $n$ of the equations. At first sight, the projection of $x^*$ does not seem to be a problem, and all the coefficients of these equations can be kept integer and polynomial in $\varphi$.

So that should reduce your question to the following one:

For systems of linear equations $Cx=d$ (where $C$ is a $n\times n$ integer matrix, and the maximal entry in $C$ and $d$ is $\varphi$) with a unique solution $x^*$, is it true that $x^*$ is polynomial in $n$ and $\varphi$?

EDIT. As pointed out by Kristoffer Arnsfelt Hansen, it is of course useless to consider more than $n$ linear equations.

  • $\begingroup$ If $x$ is the unique solution to $Cx=d$, then obviously $x$ is also the unique solution to a subsystem consisting of $n$ of the equations. $\endgroup$ Commented Jan 7, 2015 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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