Discalimer:
The approach below may be usefull to prove P=NP. I would understand down-voting.
Many NP-complete problems can be encoded in the system of polynomial equations. Some examples are in the introduction here. Basically the idea is to encode binary variables in the equations $f_k= x_k^2-1= 0$, or $f_k = x_k^2-x_k=0$, and add one or more equations ($g_k=0 $) encoding satisfiability problem. Since the system can have exponentially many solutions finding them is hard. On the other hand, we can try to figure out if the system has solutions at all. One of the approaches is to use Nulstellensatz certificate, e.g. find the set of polynomials $P_k, P'_k \in \mathbb{K}[x_1,...x_n]$, where $\mathbb{K} $ is an algebraically closed field, for example $\mathbb{C} $ such that the following equation is satisfied $1= \sum_k P_k f_k +\sum_m P'_m g_m$. The problem with this approach is that one need very high degree polynomials $P_k, P'_k $ and the certificate has exponentially many monomials. The intuition here is following. The problem is hard since all variables are influencing other variables, otherwise the problem can be split into independent subproblems. Since all of them are important the term with monomial $x_1 ... x_n$ has to appear in the certificate. That lead to the certificate of degree $n$, which has too many monomials.There is no clear way of selecting right monomials, and we need to use all of them. So the problem is that by increasing the degree of certificate the "mixing" of variables is too slow - we introduce too much noise - too many problem irrelevant tautologies!!! And we need a way to speed-up mixing of the variables.
We do usual trick of linearizing quadratic equations in terms of quadratic monomials (for 3-SAT we need cubic monomials), e.g. $y_{x_k,x_m}= x_k x_m,\ k, m = 0..n,\ x_0=1 $. This linear system has $\approx n^2$ linear variables (monomials), and $\approx n$ equations, e.g. highly under-complete. The solution of this (homogenised) linear system is $\approx n^2 $ dimensional projective space. The original system has a solution iff there is a point $c \in \mathbb{C}^{\approx n^2}$ in this projective space such that all corresponding equations on $y_{x_k,x_m} = y_{x_0,x_k} y_{x_0, x_m}, y_{0,0}=1$ are satisfied. These are quadratic equations on $c$, so we can write all the quadratic in $c$ constraints $y_{x_k,x_m} y_{x_p,x_q}= y_{x_k,x_p} y_{x_m,x_q}= y_{x_k,x_q} y_{x_p,x_m}$ (tautologies). Therefore, we have $\approx \frac{2}{3} n^4 $ quadratic equations with $\approx n^2 $ indeterminates $c_k$. Now we have equivalent, in terms of satisfiability, system of quadratic equations with $O(n^4)$ equations and $O(n^2)$ variables $c_k$, In other words, now we have $O(1)$ equations in terms of the number of quadratic in monomials, and the system is almost complete.
Now we can write Nulstellensatz certificate for the new system of tautologies in terms of $c_k$.
Q1. Does anyone see a simple way of proving fixed certificate degree for the new "almost complete" system?
Any relevant references are appreciated.
