ECCC-Report TR23-007https://eccc.weizmann.ac.il/report/2023/007Comments and Revisions published for TR23-007en-usFri, 03 Feb 2023 10:33:12 +0200
Paper TR23-007
| Extended Nullstellensatz proof systems |
Jan Krajicek
https://eccc.weizmann.ac.il/report/2023/007For a finite set $\cal F$ of polynomials over a fixed finite prime field of size $p$ containing all polynomials $x^2 - x$, a Nullstellensatz proof of the unsolvability of the system
$$
f = 0\ ,\ \mbox{ all } f \in {\cal F}
$$
is a linear combination $\sum_{f \in {\cal F}} \ h_f \cdot f$ that equals to $1$ in the ring of polynomials. 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 {\em extended} NS proof systems: these systems prove the unsolvability of $\cal F$ by proving the unsolvability of a bigger set ${\cal F}\cup {\cal E}$, where set $\cal E$ may use more variables $r$ and contains polynomials $r^p - r$ for them, and satisfies the following soundness condition:
-- Any $0,1$-assignment ${\overline a}$ to variables ${\overline x}$ can be appended by an assignment ${\overline b}$ to variables $\overline r$ such that for all $g \in {\cal E}$ it holds that $g(\overline a, \overline b) = 0$.
We define a notion of pseudo-solutions of $\cal 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 in Buss et al. (1996/97). Further we give a combinatorial example of $\cal F$ and candidate pseudo-solutions based on the pigeonhole principle.Fri, 03 Feb 2023 10:33:12 +0200https://eccc.weizmann.ac.il/report/2023/007