I have heard it said that QP problems $$\min f(x) = \frac 12 x^TAx + b^T x$$ $$x \in P$$ where $A$ is a symmetric matrix and $P$ is a polyhedron can all be solved exactly and in finite time (or it can be shown that there is no minimum in finite time). I can solve a few of the cases, but not all of them.
I have done a couple of cases below, but they all involve $P$ being bounded. I'm not sure how to deal with $P$ being unbounded. I think there are two cases to do when $P$ is unbounded: $f$ is bounded below on $P$, and $f$ is unbounded below on $P$.
Case 1: $P$ is bounded, $A$ is P.S.D.
By boundedness a minimum exists. The minimum can be found by analyzing the KKT points. Indeed, we have $\nabla^2_{xx} L = Q$ is P.S.D., so every KKT point satisfies the SOSC, so is a local minimum . But $f$ is convex, so any local minimum is global.
Finding the KKT points for quadratic problems reduces to solving a bunch of systems of linear equations, which can be done exactly in finite time.
Case 2: $P$ is bounded, $A$ is N.S.D.
In this case $f(x)$ is concave, and it is well-known that the minimum of a concave function over a polytope occurs at a vertex. Therefore we could find the minimum by examining the vertices, which can be done exactly in finite time to find.
Case 3: $P$ is bounded, $A$ is indefinite.
I know that the minimum will occur at a boundary point of the domain, but I don't know how to go further.