Conférence d’Avi Wigderson

The P vs. NP problem: Internet security, efficient computations and the limits of human knowledge

Avi Wigderson

Mardi 23 mars à  16h30

Salle Dussane

Ecole normale supérieure, 45 rue d’Ulm, 75005 Paris

Avi Wigderson est un mathématicien et informaticien israélien, professeur à  l’Institute for Advanced Study à  Princeton. Il est spécialiste de mathématiques «discrètes » , tout particulièrement des liens entre mathématiques et informatique. Il a reçu deux prix très importants, le prix Nevannlina en 1994 pour ses travaux sur la complexité, et le prix Gà¶del en 2009 pour le produit «zigzag » de graphes. Sa conférence sera donnée en anglais. Elle devrait intéresser des jeunes étudiants et des lycéens curieux.

Résumé.

The P versus NP problem is a precise, easy to state mathematical problem.
Yet it stands unique in the philosophical meaning, and the impacts of its resolution.

If P equals NP, then we can hope to quickly answer most other mathematical and scientific challenges we face. If P does not equal NP, we can hope to make the security of electronic interactions unconditional.

In the talk I’ll formulate the P versus NP problem, and explain these far reaching connections. I’ll describe the research it has spun in Computational Complexity, and report on the attempts to resolve it.