On complexity of linear programming with quadratic equality/inequality constraints? Feasibility test in Linear programming is in $P$ and in convex quadratic programming is in $P$. What is the maximum $k$ such that $n$-variable $m=poly(n)$ linear constraint feasibility test with $k$ many quadratic (not necessarily convex constraints)


equality constraints in $P$?
inequality constraints in $P$?



  Can $k=\Omega(poly(n))$ hold in both cases? At least can $k&gt;0$ hold at least for $1.$?
A famous result by Motzkin and Straus expresses the $k$-clique problem as the maximization of a quadratic function subject to a system of linear constraints.  In particular, they prove:


  Let $G$ be a graph with vertices $1,\ldots,n$ and edge set $E$. 
  Then $G$ contains a $k$-clique,
  if and only if there exist real numbers $x_1,\ldots,x_n$ 
  that satisfy the quadratic constraint
  $$\sum_{(i,j)\in E}x_ix_j \ge \frac12\left(1-\frac1k\right)$$
  together with the linear constraints $\sum_{i=1}^nx_i=1$ 
  and $x_1,\ldots,x_n\ge0$.



Since the $k$-clique problem is NP-hard, this implies that feasibility testing for a linear program plus a single quadratic inequality constraint is NP-hard.
If the graph $G$ contains a $k$-clique $C$, then for $i\in C$ we may set $x_i=1/k$ and for $i\notin C$ we may set $x_i=0$. 
Note that the resulting point $x$ satisfies all constraints in the feasibility problem with equality. 
This yields that also feasibility testing for a linear program plus a single quadratic equality constraint is NP-hard.


Reference:
T.S. Motzkin and E.G. Straus (1965), "Maxima for graphs and a new proof of a theorem of Turán." Canadian Journal of Mathematics 17, pp 533–540.