The paper considers different classes of nonconvex quadratic problems that can be solved in polynomial time. It presents an algorithm for the problem of minimizing the product of two linear functions over a polyhedron P in Rn. The complexity of the algorithm depends on the number of vertices of the projection of P onto the R2 space. In the worst-case this algorithm requires an exponential number of steps but its expected computational time complexity is polynomial. In addition, the paper gives a characterization for the number of isolated local minimum areas for problems of this form. Furthermore, it considers indefinite quadratic problems with variables restricted to be nonnegative. These problems can be solved in polynomial time if the number of negative eigenvalues of the associated symmetric matrix is fixed.
