Advertising Console

    [METRIC 2011] Avi Wigderson Popular's talk at ENS Ulm

    Nicolas Schabanel

    par Nicolas Schabanel

    207 vues
    METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France)
    Workshop on Expanders and derandomization (March 21-25, 2011)
    Mar 23, 16:30-17:30 - Avi Wigderson (IAS Princeton)
    Popular's talk at the École Normale Supérieure de Paris
    The P vs. NP problem: Internet security, efficient computations and the limits of human knowledge
    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.