Extended Nullstellensatz proof systems

Abstract:

For a finite set $\mathcal {F}$ of polynomials from ${\mathbf {F}_{p}[\overline x]}$ ($p$ is a fixed prime) containing all polynomials $x^2 - x$, a Nullstellensatz proof of the unsolvability of the system \begin{equation*} f = 0, \text { all } f \in \mathcal {F} \end{equation*} in $\mathbf {F}_{p}$ is an ${\mathbf {F}_{p}[\overline x]}$-linear combination $\sum _{f \in \mathcal {F}} \ h_f \cdot f$ that equals to $1$ in ${\mathbf {F}_{p}[\overline x]}$. The measure of complexity of such a proof is its degree: $\max _f deg(h_f f)$.

We study the problem to establish degree lower bounds for some extended NS proof systems: these systems prove the unsolvability of $\mathcal {F}$ (in $\mathbf {F}_{p}$) by proving the unsolvability of a bigger set $\mathcal {F}\cup \mathcal {E}$, where the set $\mathcal {E}\subseteq {\mathbf {F}_{p}[\overline x, \overline r]}$ contains all polynomials $r^p - r$ and satisfies the following soundness condition:

Any $0,1$-assignment $\overline a$ to variables $\overline x$ can be appended by an $\mathbf {F}_{p}$-assignment $\overline b$ to variables $\overline r$ such that for all $g \in \mathcal {E}$ it holds that $g(\overline a, \overline b) = 0$.

We define a notion of pseudo-solutions of $\mathcal {F}$ and prove that the existence of pseudo-solutions with suitable parameters implies lower bounds for two extended NS proof systems ENS and UENS defined by Buss et al [Comput. Complexity 6 (1996/97), pp. 256–298]. Further we give a combinatorial example of $\mathcal {F}$ and candidate pseudo-solutions based on the pigeonhole principle.