On complexity of linear programming with quadratic equality/inequality constraints?

Question

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)

1. equality constraints in $P$?

2. inequality constraints in $P$?

Can $k=\Omega(poly(n))$ hold in both cases? At least can $k>0$ hold at least for $1.$?

Answer 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.