Séminaire des Doctorant·e·s :

Le 12 mai 2011 à 17h30 - Salle 331

Présentée par Heide-Jørgensen Uffe - 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.