Séminaire Algèbre Géométrie Algébrique Topologie Algébrique
jeudi 23 juin 2011 à 14:00 -
Uffe Heide-Jørgensen (Institut for Matematiske Fag Aarhus Universitet, Danemark et I3M)
Complexity theory and algebraic geometry
I will give a short introduction to the two complexity classes P and NP, known from theoretical computer science, along with a more thorough introduction to Valiant's algebraic analogues VP and VNP. Furthermore I will explain why the polynomials known as the determinant and the permanent are important in relation to VP resp. VNP, and why it is interesting to link the two polynomials to each other. If time permits it I will also talk about the more general term immanants which the determinant and the permanent are special cases of.