1
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

If your system is linear, Gaussian elimination will tell you everything you want.

In contrast, given a system of quadratic equations, it is NP-hard to determine whether it has any solution. I'm not sure what is your definition of overdetermined and underdetermined, but the corresponding problems are likely also NP-hard, by reduction to the above-mentioned problem.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.