Séance Séminaire

Séminaire des Doctorant·e·s

jeudi 12 mai 2011 à 17h30 - Salle 331

Uffe Heide-Jørgensen (Institut for Matematiske Fag Aarhus Universitet, Danemark et I3M)

Complexity Classes and the Permanent and Determinant problem

The first Millenium Prize Problem stated by the Clay Mathematics Institute is the P versus NP problem, which lies on the borderline between theoretical computer science and mathematics. As the notion of the complexity classes P and NP is related to computer science rather than traditional mathematics, I will give a brief introduction to these along with the problem. The two polynomials The Determinant and The Perminant are closely related to P and NP respectively. I will also talk a bit about these polynomials and how they may give an answer the P vs. NP problem.