Computer Algebra, Combinatorics, and Complexity: Hilbert's Nullstellensatz and NP-complete Problems
Susan Margulies, Rice (CAAM)

Systems of polynomial equations over an algebraically-closed field K can be used to concisely express combinatorial decision problems. In this representation, a combinatorial problem is feasible (e.g., a graph is 3-colorable, Hamiltonian, etc.) if and only if a related system of polynomial equations has a solution over K. If the system of polynomial equations has no solution, then Hilbert's Nullstellensatz yields a certificate that the underlying combinatorial problem is infeasible. In this dissertation, we investigate an algorithm aimed at proving combinatorial infeasibility based on the experimentally-observed low degree of Hilbert's Nullstellenatz and large-scale, sparse linear algebra computations over K.

We explore the Nullstellensatz Linear Algebra algorithm (NulLA) from both a computational and a theoretical perspective. From the computational perspective, we compare computations over the rationals to computations over finite fields; we discuss mathematical ideas for optimizing NulLA ranging from the algebraic to the probabilistic, and we report on experiments proving the non-3-colorability of graphs with thousands of vertices and tens of thousands of edges.

From a theoretical perspective, we observe that if an NP-complete combinatorial decision problem (e.g. graph 3-colorability) is represented as a system of polynomial equations, the resulting infeasibility certificate associated with an infeasible instance is a coNP certificate. Thus, if P != NP and NP != coNP, there must exist an infinite family of instances (e.g. an infinite family of graphs) where the minimum-degree of the associated Nullstellensatz certificates grows linearly in the input size and the certificates contain a super-polynomial number of monomials. In the case of the independent set decision problem, we show that the minimum-degree of the associated Nullstellensatz certificate proving the non-existence of an independent set of size k is equal to the size of the largest independent set in the graph. Moreover, every such Nullstellensatz certificate contains one monomial for each independent set in the graph.