I'm trying to learn the complexity of a quadratic program in the form of:
given only $x*y$
What I want to learn is that, is there a polynomial time algorithm for this quadratic progamming definiton by any means such as ellipsoid method, simplex method, interior point method? I assume that stochastic optimization technics can only provide good approximations (it can even not be possible if the problem is NP-Hard). There are many complexity results which vary according to an even smallest problem definition and it becomes confusing as I dig further. For example a result from Pardalos et.al states "Quadratic programming with one negative eigenvalue is NP-hard". But there is also Nesterov & Nemirovski's result: polynomial-time interior-point methods for nonlinear convex programming". In theory, convexity of the definition can make it tractable again. So what is the situation for this exact definition?
I know that for the large problem sizes (for example a large bit size like 50) , even though the underlying method is efficient there can be issues related to asymptotical efficiency, mostly because of rounding errors. Can advanced methods like interior point get an exact solution for a large problem size or can we only expect an approximation?
Confining all the variables to integers makes this one an integer non-linear program. As known, almost all integer programs are NP-Hard. Does this definition also suffer from this fact, or any advanced method (not necessarily limited to those mentioned above) can also find a global integer optimum? Also I would like to learn if there's an efficient exact real-world solver for this type of problem? Due to the hardness assumptions mentioned for both non-linear and integer programming, I assume that the integer version is much beyond tractibility (perhaps NP-Hard).