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

<p>Unfortunately, I wasn't able to find a recent survey of algebraic proof systems. Toni Pitassi has an old <a href="http://www.cs.toronto.edu/~toni/Papers/pitassi-algebraic.ps" rel="nofollow">survey</a>, but there are many results not mentioned there. There is some material in the more general <a href="http://homes.cs.washington.edu/~beame/papers/eatcs-survey.ps" rel="nofollow">survey</a> by Paul Beame and Toni Pitassi. Some more recent results are referenced in a <a href="http://www.math.cas.cz/~pudlak/fall-school09.pdf" rel="nofollow">lecture</a> by Pavel Pudlák.</p>

CC BY-SA 3.0
2012-12-05T15:32:24.543Z
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
CC BY-SA 3.0
2012-12-05T20:26:31.517Z
Also see Paul Beame, "[Proof Complexity](http://www.cs.washington.edu/homes/beame/papers/lec.ps)", 2004. Sasha Razbarov has a good bibliography [here](http://people.cs.uchicago.edu/~razborov/teaching/winter09.html).
Kaveh
CC BY-SA 3.0
2012-12-06T08:53:11.107Z
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
CC BY-SA 3.0
2012-12-06T14:53:50.460Z
@mkatkov They belong to whatever you want them to, though probably not linear algebra, but rather commutative algebra.
Yuval Filmus
CC BY-SA 3.0
2012-12-05T15:09:30.980Z
2012-12-05T15:09:30.980Z
Yuval Filmus
<p>Discalimer:</p>

<p>The approach below may be usefull to prove P=NP. I would understand down-voting.</p>

<p>Many NP-complete problems can be encoded in the system of polynomial equations. Some examples are in the introduction <a href="http://homepages.cwi.nl/~monique/files/moment-ima-update-new.pdf" rel="nofollow noreferrer">here</a>. 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 <a href="http://www.math.ucdavis.edu/~deloera/RECENT_WORK/jsc09_issac08.pdf" rel="nofollow noreferrer">to use <em>Nulstellensatz</em> certificate</a>, 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.<a href="https://cstheory.stackexchange.com/questions/14073/semiprime-factorization-groebner-bases-and-a-nullstellensatz-certificate">There is no clear way of selecting right monomials</a>, 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.</p>

<p>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.</p>

<p>Now we can write <em>Nulstellensatz</em> certificate for the new system of tautologies in terms of $c_k$. </p>

<p><strong>Q1. Does anyone see a simple way of proving fixed certificate degree for the new "almost complete" system?</strong></p>

<p>Any relevant references are appreciated.</p>

CC BY-SA 3.0
2012-12-05T17:47:20.123Z
What do you mean by "fixed certificate degree"?
Yuval Filmus
CC BY-SA 3.0
2012-12-05T17:55:17.973Z
Certificate of fixed degree that does not depend on n.
mkatkov
CC BY-SA 3.0
2012-12-05T19:56:59.153Z
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
CC BY-SA 3.0
2012-12-06T09:22:40.570Z
@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
<cc.complexity-theory>
Proof of Nullstellensatz certificate degree
mkatkov
# Proof of Nullstellensatz certificate degree

(Asked by: username_0 on 2012-12-05)

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](http://homepages.cwi.nl/~monique/files/moment-ima-update-new.pdf). 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](http://www.math.ucdavis.edu/~deloera/RECENT_WORK/jsc09_issac08.pdf), 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](https://cstheory.stackexchange.com/questions/14073/semiprime-factorization-groebner-bases-and-a-nullstellensatz-certificate), 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.

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: What do you mean by "fixed certificate degree"?  
> **username_0**: Certificate of fixed degree that does not depend on n.  
> **username_1**: 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.  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_1 on 2012-12-05. Score: 3 | Accepted 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](http://www.cs.toronto.edu/~toni/Papers/pitassi-algebraic.ps), but there are many results not mentioned there. There is some material in the more general [survey](http://homes.cs.washington.edu/~beame/papers/eatcs-survey.ps) by Paul Beame and Toni Pitassi. Some more recent results are referenced in a [lecture](http://www.math.cas.cz/~pudlak/fall-school09.pdf) by Pavel Pudlák.

> **Comments:**
> **username_0**: 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.  
> **username_2**: Also see Paul Beame, "[Proof Complexity](http://www.cs.washington.edu/homes/beame/papers/lec.ps)", 2004. Sasha Razbarov has a good bibliography [here](http://people.cs.uchicago.edu/~razborov/teaching/winter09.html).  
> **username_0**: just checking my understanding - 15 linearly independent homogeneous quadratic equations over 5 variables is belong to linear algebra, or to proof complexity, or both?  
> **username_1**: @mkatkov They belong to whatever you want them to, though probably not linear algebra, but rather commutative algebra.  

---

