# Reduction from vertex-cover to system of quadratic equations

Define $$\text{SQE}=\{S\ |\ S\ \text{is a system of quadratic equations with real solutions}\}$$ and $$\text{VC}=\{G\ |\ G\ \text{is a simple undirected graph with a vertex cover}\ \leq k\}$$

I am trying to prove that SQE is NP-hard via the reduction $$VC\leq_P SQE$$.

My attempt:

Given a $$G=(V,E)$$, we want to construct some system of quadratic equations $$S$$, such that $$G\in VC$$ if and only if $$S$$ has real solutions.

For each $$u\in V$$ introduce the variable $$x_u$$. We want $$x_u=1$$ represent vertex $$u$$ being in the vertex cover and $$x_u=0$$ to represent it is not. How can we capture, using a quadratic equation, the fact that in a vertex-cover every edge is covered?

For each edge $$\{u,v\}\in E$$ we introduce the following inequality. $$x_u + x_v \geq 1$$ However, we are not allowed inequalities. With some thought I came up with the following to replace the inequality. $$x_u+x_v-x_ux_v=1$$ This is equal to $$1$$ if and only if either $$u$$ or $$v$$ or both are in the vertex-cover.

However, the domain for an $$x_u$$ is the reals, but we want to operate in $$\{0,1\}$$, so that each vertex is either chosen or not. Therefore, we can introduce for each $$v\in V$$ the following equation $$x_v^2 = x_v$$ which has solutions $$0$$ or $$1$$ only.

Now we just need to limit the number of vertices in the vertex-cover to $$\leq k$$. Using an inequality this is written $$\sum_{u\in V}{x_u}\leq k$$. I now need some quadratic function $$f(x_{u_1}, x_{u_2}, ..., x_{u_n}) = c$$ if and only if $$\sum_{u\in V}{x_u}\leq k$$. But I can't figure out what it should look like.

Add $$k$$ Boolean variables $$z_1,\ldots,z_k$$ and the constraint $$\sum_{u \in V} x_u + \sum_{i=1}^k z_i = k$$.

(Optimization: add $$\ell = \lceil \log_2 k \rceil$$ Boolean variables $$w_1,\ldots,w_\ell$$ and the constraint $$\sum_{u \in V} x_u + \sum_{j=1}^\ell 2^{j-1} w_j = k$$.)

• Ohhh. I am a dummy haha. Thank you. Commented Apr 3, 2022 at 16:37