Spring 2016

Hilbert's Nullstellensatz Certificates of Infeasibility for Combinatorial Problems

Thursday, March 31st, 2016 4:15 pm5:00 pm

Add to Calendar

Systems of polynomial equations can be used to compactly and elegantly model combinatorial problems in such a way that if a given combinatorial property is not satisfied, then the system of polynomial equations has no solution. If a system of polynomial equations has no solution, there exists a very specific algebraic proof of infeasibilty via the famous Hilbert's Nullstellensatz. In this talk we compare and contrast the complexity of Hilbert's Nullstellensatz certificates when the underlying combinatorial problem is NP-complete (such as Partition), as compared to problems known to be in P (such as 2-colorability or Matching).