Extended Nullstellensatz proof systems
share
For a finite set F of polynomials over fixed finite prime field of size p containing all polynomials x^2 - x a Nullstellensatz proof of the unsolvability of the system f = 0 , f ∈ F in the field is a linear combination ∑_f ∈ F h_f · f that equals to 1 in the ring of polynomails. 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 F by proving the unsolvability of a bigger set F∪ E, where set E may use new variables r and contains all polynomials r^p - r, and satisfies the following soundness condition: – - Any 0,1-assignment a to variables x can be appended by an assignment b to variables r such that for all g ∈ E it holds that g(a, b) = 0. We define a notion of pseudo-solutions of 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 F and candidate pseudo-solutions based on the pigeonhole principle.
READ FULL TEXT