# Proof of Nullstellensatz certificate degree

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.

-
What do you mean by "fixed certificate degree"? –  Yuval Filmus Dec 5 '12 at 17:47
Certificate of fixed degree that does not depend on n. –  mkatkov Dec 5 '12 at 17:55
Well, take a formula for which a strong degree lower bound exists. Now consider your modified system. Suppose it had a solution with small degree. Substitute $y_{x_k,x_m} = x_k x_m$. This at most doubles the degree. Presumably the result is a solution for the original system. –  Yuval Filmus Dec 5 '12 at 19:56
@Yuval y is projected on c (that have smaller dimension), if you have a certificate on c it does not necessarily mean you can write certificate on y or on x, if I understand correctly what are you saying. –  mkatkov Dec 6 '12 at 9:22

## 1 Answer

The research area relevant to your question is propositional proof complexity, more specifically algebraic proof systems. Nullstellensatz is in fact only one of a family of proof systems which includes also the polynomial calculus (PC), polynomial calculus with resolution (PCR), and a proof system which has received some notice from a surprising directions, the sum of squares (SoS) system.

Unfortunately, I wasn't able to find a recent survey of algebraic proof systems. Toni Pitassi has an old survey, but there are many results not mentioned there. There is some material in the more general survey by Paul Beame and Toni Pitassi. Some more recent results are referenced in a lecture by Pavel Pudlák.

-
Dear Yuval, as far as I understand all these systems are weak to even prove pigeon hole principle in a reasonable time (Don't know about SoS, but guess it is weak too). The whole point here is that there are too many tautologies that should be represented in the system but are irrelevant to the problem. I may be wrong, and the problem is more basic, and lay within propositional proof complexity. –  mkatkov Dec 5 '12 at 15:32
Also see Paul Beame, "Proof Complexity", 2004. Sasha Razbarov has a good bibliography here. –  Kaveh Dec 5 '12 at 20:26
just checking my understanding - 15 linearly independent homogeneous quadratic equations over 5 variables is belong to linear algebra, or to proof complexity, or both? –  mkatkov Dec 6 '12 at 8:53
@mkatkov They belong to whatever you want them to, though probably not linear algebra, but rather commutative algebra. –  Yuval Filmus Dec 6 '12 at 14:53