0
$\begingroup$

My algorithm solves the following problem:

$n\in\mathbb{N} \land n\ge1$

$\{v_1, \ldots , v_n\}\subset\mathbb{Q}$

$ \begin{eqnarray} \left\{ \begin{array}{} \square\cdot\square\cdot\square = 0 \\ \vdots \\ \square\cdot\square\cdot\square = 0 \\ \end{array} \right. \end{eqnarray} $

$\square\in\{v_1,\ldots,v_n,1-v_1,\ldots,1-v_n\}$

The algorithm works as follows:

First of all open up all brackets (), i.e. eliminate them so they are not appear in the system anymore without changing the equations, i.e. the consistency of the system.

This part should take polynomial time I guess.

As you can see all equations are equal to zero, so the algorithm solves the problem by doing the substitution method.

It chooses the smallest equation and substitutes it in a larger equation and thus it eliminates and removes subexpressions and simplify the system.

The algorithm repeats the substitution method until it cannot be done anymore.

If $1=0$ was discovered then return as answer: The system is inconsistent.

Otherwise return as answer: The system is consistent.

For example let's apply my algorithm to the following system of nonlinear equations:

$ \begin{eqnarray} \left\{ \begin{array}{} v_1 \cdot v_2 \cdot v_3 = 0 \\ (1-v_1) \cdot v_2 \cdot v_3 = 0 \\ v_1 \cdot (1-v_2) \cdot v_3 = 0 \\ (1-v_1) \cdot (1-v_2) \cdot v_3 = 0 \\ v_1 \cdot v_2 \cdot (1-v_3) = 0 \\ (1-v_1) \cdot v_2 \cdot (1-v_3) = 0 \\ v_1 \cdot (1-v_2) \cdot (1-v_3) = 0 \\ (1-v_1) \cdot (1-v_2) \cdot (1-v_3) = 0 \\ \end{array}{} \right. \end{eqnarray} $

here in this example $n=3$, because there are only three variables, which are $v_1$, $v_2$ and $v_3$.

First of all let's open up all the brackets (), so they are not appear in the system. After doing that the system should look like this:

$ \begin{eqnarray} \left\{ \begin{array}{} v_1 \cdot v_2 \cdot v_3 = 0 \\ v_2 \cdot v_3 - v_1 \cdot v_2 \cdot v_3 = 0 \\ v_1 \cdot v_3 - v_1 \cdot v_2 \cdot v_3 = 0 \\ v_3 - v_2 \cdot v_3 - v_1 \cdot v_3 + v_1 \cdot v_2 \cdot v_3 = 0 \\ v_1 \cdot v_2 - v_1 \cdot v_2 \cdot v_3 = 0 \\ v_2 - v_2 \cdot v_3 - v_1 \cdot v_2 + v_1 \cdot v_2 \cdot v_3 = 0 \\ v_1 - v_1 \cdot v_3 - v_1 \cdot v_2 + v_1 \cdot v_2 \cdot v_3 = 0 \\ 1 - v_3 - v_2 - v_1 + v_2 \cdot v_3 + v_1 \cdot v_3 + v_1 \cdot v_2 - v_1 \cdot v_2 \cdot v_3 = 0 \\ \end{array}{} \right. \end{eqnarray} $

Now let's substitute $v_1 \cdot v_2 \cdot v_3 = 0$ from the first equation and we get:

$ \begin{eqnarray} \left\{ \begin{array}{} v_1 \cdot v_2 \cdot v_3 = 0 \\ v_2 \cdot v_3 - 0 = 0 \\ v_1 \cdot v_3 - 0 = 0 \\ v_3 - v_2 \cdot v_3 - v_1 \cdot v_3 + 0 = 0 \\ v_1 \cdot v_2 - 0 = 0 \\ v_2 - v_2 \cdot v_3 - v_1 \cdot v_2 + 0 = 0 \\ v_1 - v_1 \cdot v_3 - v_1 \cdot v_2 + 0 = 0 \\ 1 - v_3 - v_2 - v_1 + v_2 \cdot v_3 + v_1 \cdot v_3 + v_1 \cdot v_2 - 0 = 0 \end{array}{} \right. \end{eqnarray} $

Now let's substitute $v_2 \cdot v_3 = 0$, $v_1 \cdot v_3 = 0$ and $v_1 \cdot v_2 = 0$:

$ \begin{eqnarray} \left\{ \begin{array}{} v_1 \cdot v_2 \cdot v_3 = 0 \\ v_2 \cdot v_3 = 0 \\ v_1 \cdot v_3 = 0 \\ v_3 - 0 - 0 = 0 \\ v_1 \cdot v_2 = 0 \\ v_2 - 0 - 0 = 0 \\ v_1 - 0 - 0 = 0 \\ 1 - v_3 - v_2 - v_1 + 0 + 0 + 0 = 0 \end{array}{} \right. \end{eqnarray} $

Now let's substitute $v_3 = 0$, $v_2 = 0$ and $v_1 = 0$:

$ \begin{eqnarray} \left\{ \begin{array}{} v_1 \cdot v_2 \cdot v_3 = 0 \\ v_2 \cdot v_3 = 0 \\ v_1 \cdot v_3 = 0 \\ v_3 = 0 \\ v_1 \cdot v_2 = 0 \\ v_2 = 0 \\ v_1 = 0 \\ 1 - 0 - 0 - 0 = 0 \end{array}{} \right. \end{eqnarray} $

And we have got $1=0$ on the last equation so this system is inconsistent and we're done.

Now my question is:

What is the complexity of my algorithm?

I guess that it's exponential, i.e. all the substitutions take exponential time, but I have no proof.

$\endgroup$
  • 1
    $\begingroup$ It looks likely that a transcript of your algorithm can be modified to provide a refutation of the formula (in case it's unsatisfiable) in the propositional proof system Resolution. It is known that some formulas (for example, various forms of the pigeonhole principle) require exponentially long proofs in Resolution. This suggests that your algorithm will perform poorly on such examples. $\endgroup$ – Yuval Filmus Aug 20 '17 at 15:04
  • $\begingroup$ @Yuval Filmus So my guess is probably correct according to your comment that my algorithm runs in exponential time. Your comment can be a very relevant part in the true answer to my question. $\endgroup$ – Farewell Stack Exchange Aug 20 '17 at 16:27
  • $\begingroup$ Well it is difficult for me to see the complexity of my algorithm in general. I never was good at analyzing complexity of algorithms and their correctness too. I even failed in the test of course algorithms because of all the questions to analysis algorithms. They were worth too many points in the exam. I just afraid that my algorithm runs exponentially slow as how resolution algorithm does exactly. $\endgroup$ – Farewell Stack Exchange Aug 20 '17 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.