# Determine whether the system of equations is underdetermined or overdetermined

Suppose I have a set of $$n$$ equations (each equation can be linear or quadratic).

I want to determine whether the system is underdetermined or overdetermined. For example, $$a_1=2,a_1=3$$ is overdetermined since I already know $$a_1$$ from the first equation, while $$a_1+a_2+a_3=1,a_1^2+a_2=5$$ is underdetermined.

If I know which variables are presented in each equation, is it possible to tell whether the system is underdetermined or overdetermined?

For now I'm thinking about the following algorithm:

1. Determine the number of variables in each equation (let it be $$m$$).
2. Add weight $$\frac{1}{m}$$ to each variable presented.
3. After examining all equations the system is overdetermined when any weight is greater than two or sum of all weights is greater than $$n$$. It is underdetermined if any weight is less than one or sum of all weights is less than $$n$$.

For example, consider the above system $$a_1+a_2+a_3=1,a_1^2+a_2=5$$.

First equation: $$w_{a_1}=\frac{1}{3}$$, $$w_{a_2}=\frac{1}{3}$$, $$w_{a_3}=\frac{1}{3}$$.

Second equation: $$w_{a_2}=\frac{1}{2}$$, $$w_{a_2}=\frac{1}{2}$$.

Total: $$w_{a_1}=\frac{5}{6}$$, $$w_{a_2}=\frac{5}{6}$$, $$w_{a_3}=\frac{1}{3}$$.

Thus, the system is underdetermined.

There are cases, that due to the above definition, the system can be both overdetermined and underdetermined: $$a_1=2,a_1=3,a_1+a_2+a_3=3$$. We consider such equations overdetermined.

Are there any other ideas?

To see that this problem is indeed NP-hard, we show that quadratic equations can encode Boolean circuits. Suppose that we have a Boolean circuit on inputs $$x_1,\ldots,x_n$$ with output $$r$$. We will have equations $$x_i^2 = x_i$$ for all $$i$$, and for each gate $$g$$, the equation $$g^2 = g$$ together with:
• If $$g = \lnot h$$ then $$g = 1-h$$.
• If $$g = a \land b$$, the equations $$g + G = a+b$$ (where $$G$$ is a new variable), $$G^2 = G$$, and the two equations $$g(1-a) = g(1-b) = 0$$.
• If $$g = a \lor b$$, the equations $$g + G = a+b$$ (where $$G$$ is a new variable), $$G^2 = G$$, and the two equations $$a(1-g) = b(1-g) = 0$$.
If we add the equation $$r = 1$$, then every satisfying assignment for the circuit (that is, an assignment which causes the circuit to output $$1$$) lifts to a unique solution of the system, and these are the only solutions of the system. In particular, this gives a reduction from SAT to our problem.