# 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)

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.$?

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.

• Does the same argument work for GI on why I cannot solve GI by just $PGP′=H$ on constraint permutation $P$ is generated by linear constraints $$\forall i: \sum_{j = 1}^n{P_{ij}} = 1$$ $$\forall j: \sum_{i = 1}^n{P_{ij}} = 1$$ $$\forall i, j: P_{ij} \geq 0$$ where $G$ and $H$ are adjacency matrices of graphs whose isomorphisms need to be tested?.
– Mr.
Apr 25 '18 at 13:46
• For a permutation matrix $P$, you can write $PG = HP$ instead of $PGP^T = H$. This gives a linear program together with the constraint you give, and you can solve it. But the solution will be a doubly stochastic matrix $P$, not necessarily a permutation matrix. While you can write a doubly stochastic $P$ as a convex combination of permutation matrices, there is no guarantee any of them will be an isomorphism. Apr 26 '18 at 5:05