Originator: Noga Alon (presented by Dan Schreiber - REGS 2009)
Background: Let F be a field, and let ƒ be a polynomial in variables x1,...,xn over F whose degree is ∑i=1n ti. The Combinatorial Nullstellensatz [Al] states that if the coefficient of ∏i=1n xiti in ƒ is nonzero, and S1,...,Sn are subsets of F with |Si| > ti for all i, then there exists s∈∏Si such that ƒ(s)≠0.
The proof of the Combinatorial Nullstellensatz is non-constructive. The computational problem NULLSTELLENSATZ is the following: given a polynomial ƒ and sets S1,...,Sn satisfying the conditions of the theorem, find a vector s∈∏Si such that ƒ(s)≠0.
Definitions: In order to study the complexity of NULLSTELLENSATZ, we provide informal definitions of various complexity classes of problems.
P is the class of decision problems that can be solved by an algorithm whose running time is bounded by a polynomial function of the size of the input. A decision problem can be viewed as a 0,1-function ("Boolean" function) on binary strings.
NP is the class of decision problems for which "yes" answers can be confirmed in time that is polynomial in the size of the input. In terms of the corresponding Boolean function ƒ, a "verifier" function V in P and a polynomial g are required such that whenever x is a binary string, ƒ(x)=1 if and only if there exists y∈{0,1}g(|x|) such that V(x,y)=1.
FP is the class of binary relations R such that there exists a polynomial time algorithm that, given x, outputs y for which R(x,y) holds. In modeling decision problems, x and y can be viewed as the input and the "certificate", respectively, such that R(x,y)=1 if and only if y is a string that the verifier can use to show that the answer to the decision problem is "yes".
FNP is the class of binary relations R such that there exists a polynomial time algorithm that, given both x and y, determines whether R(x,y) holds. When restricted to certificates of decision problems, FNP is roughly the same as NP.
TFNP is the class of binary relations R such that (1) there exists a polynomial time algorithm that, given both x and y, determines whether R(x,y) holds, and (2) for every x, there exists y such that R(x,y) holds. Here "T" stands for "Total" and for decision problems indicates that the answer is always "yes" and is verified by an appropriate string.
NULLSTELLENSATZ belongs to TFNP, because the theorem guarantees a "yes" answer (that is, existence of s such that ƒ(s)≠0), and the correctness of s can be verified in polynomial time.
Question 1:[Al] Is there a polynomial-time algorithm for solving NULLSTELLENSATZ?
Comments: Alon says 'it seems likely that such algorithms do exist.'
In studying a class of problems, complexity theorists often seek problems in the class that, if solvable in polynomial time, yield polynomial-time algorithms for all problems in the class. Such problems are called complete for the class. There are reasons to believe that no problems are TFNP-complete.
Papadimitriou [P] developed a framework by which we might analyze the complexity of subclasses of problems of TFNP based on the type of argument that is used to prove totality. One such lemma is the parity argument, which states that every graph has an even number of odd degree nodes. We denote by PPA the subclass of TFNP whose totality is proved via the parity argument on undirected graphs.
A special case of Chévalley's Theorem considers polynomials p1,...,pn in n variables over the finite field F2. It states that if n>∑i=1m deg(pi) and (0,...,0) is a common zero of p1,...,pn, then there is another common zero (a1,...,an). Given polynomials p1,...,pn satisfying the conditions, let CHEVALLEY-MOD-2 be the computational problem of finding a nonzero solution.
CHEVALLEY-MOD-2 is in PPA, as we can prove totality by analyzing the degrees of an appropriate bipartite graph and invoking the parity argument. In general, to show membership in PPA one must prove totality either by directly using the parity argument or by using another theorem whose computational version has previously been shown to be in PPA.
Question 2: Is NULLSTELLENSATZ in PPA?
Comment: One can use the Combinatorial Nullstellensatz to prove Chévalley's Theorem, but this does not show that NULLSTELLENSATZ is in PPA. One would have to work in the other direction and prove the Nullstellensatz from Chévalley's Theorem!
References:
[Al] Noga Alon, Combinatorial Nullstellensatz. Combinatorics, Probability and Computing 8 (1999), 7-29.
[P] Christos Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences 3 (1994), 498-532.