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).