Many NP complete problems can be encoded in system of polynomial equations. For example, in partition problem one is asking whether it is possible to divide a list of integers into two lists that the sum of element of each least are equal. Given the list of elements one is looking for the element , such that .
To encode the problem into the system of polynomial equations over one need equations of the form – that will ensure variables , and the above mentioned equation . In total nonlinear equations. We can also change the variables that . In some sense this variables may be easier for the analyses later.
One way to solve this equation is to linearise it, e.g. we define a new set of variables , and we set . Now in terms of we have system of linear equations. Unfortunately, we have lost relationship between terms. Linear system does not “know” that , etc. On the other hand, if solution of the original system exists it should lay in the null space of the coefficient matrix. We will try use it. Suppose, we have null space , than if system of equations has the solution all monomials will be simultaneously expressed as a linear combination of null space vectors . The dimensionality of null space is exactly the number of quadratic monomials minus number of equations.
So far, we were looking only at second order monomials. If we go to higher order monomials we can see that . What we wrote is tautology – this is true independent of the values of . This is also true for any . So this tautologies can be written in terms of our new variables , . On the other hand, if we have , than we does not have tautology. In any case, we can write down all tautologies for up to order 4, and their expression in terms of new variables . Moreover, for each we have its linear expression in terms of unknowns . So if we expand tautologies in terms of we will get a new set of quadratic equations, that must be satisfied, if original system has a solution.
Now we already know what to do. We need to linearise the system of quadratic equations, for which we need to introduce new variables , write down the system of linear equations, find the null space of coefficient matrix, encode as a linear combination of the null space basis, and finally encode forth-order monomials in terms of new coefficient of new null space basis. Ok, we can repeat this forever, just remember to write down all quadratic tautologies in terms of known monomials (e.g. many more tautologies). What is interesting here is how changes with iterations.
Ok, I will come back here later, when I cool down and wil have more time. Note that the number of tautologies are much more (seems to be exponentially more) than the number of monomials.
Each iteration we are squaring the number of variables which encode monomials in terms of null space. Now consider only monomials with . If we have monomial of degree than only for that monomial we have , since we want to choose half variables, and one half comes from the fact that multiplication is commutative. The number of monomials is . So, assuming tautologies are linearly independent, we have , . So the lower bound is asymptotically …