Hilbert's Nullstellensatz Certificates of Infeasibility for Combinatorial Problems

on YouTube ↗39m

" summary

Models NP problems as polynomial systems and uses Hilbert's Nullstellensatz to produce infeasibility certificates; for independent set the minimum certificate has degree = α(G) and contains one monomial per independent set, so it literally counts all independent sets. For partition the certificate enumerates every partition, the degree is n or n−1 by parity, and the constructed partition matrix has determinant equal to the partition polynomial. Groebner bases work on chordal graphs; three-colorability and perfect-matching certificates show surprising, unresolved growth.

AI-written summary · about

" chapters (15)

1. 0:00Introduction
2. 0:20Overview
3. 2:10System of Polynomials
4. 3:39Hilberts Nullstellensatz
5. 5:20Measuring Complexity
6. 5:51Sample System
7. 9:18Investigating the Certificate
8. 9:56Partition Problem
9. 11:58Proof
10. 16:38Cramers Rule
11. 17:53Investigating More
12. 20:17Encoding
13. 21:18Peterson Graph
14. 26:06Infinite Family of Graphs
15. 30:48Perfect Matching