### Geometric Complexity Theory: An ambitious approach towards P versus NP

Christian Ikenmeyer

MPI-INF - D1

Joint Lecture Series

06 Sep 2017, 12:15 pm - 1:15 pm

SaarbrÃ¼cken building E1 5, room 002

Computational complexity theory is concerned with the study of the inherent
complexity of computational problems. Its flagship conjecture is the famous P
versus NP conjecture
which is one of the seven Millennium Problems of the Clay
Mathematics Institute.

To this day several thousands of computational problems are classified as NP-complete i.e. they have a polynomial time algorithm if and only if P equals NP. The practical importance of the P vs NP conjecture is at least twofold: First of all many NP-complete problems are of high practical relevance and have to be solved every day in commercial and scientific applications. Secondly if NP turned out to be P then this would break all of today's cryptographic ciphers.

Geometric complexity theory is an ambitious program initiated in 2001 by Ketan Mulmuley and Milind Sohoni towards solving the P vs NP problem by using methods from algebraic geometry and representation theory. During the last few years there has been a significant amount of research activity related to this program. In this talk I explain some basic ideas and recent developments.

To this day several thousands of computational problems are classified as NP-complete i.e. they have a polynomial time algorithm if and only if P equals NP. The practical importance of the P vs NP conjecture is at least twofold: First of all many NP-complete problems are of high practical relevance and have to be solved every day in commercial and scientific applications. Secondly if NP turned out to be P then this would break all of today's cryptographic ciphers.

Geometric complexity theory is an ambitious program initiated in 2001 by Ketan Mulmuley and Milind Sohoni towards solving the P vs NP problem by using methods from algebraic geometry and representation theory. During the last few years there has been a significant amount of research activity related to this program. In this talk I explain some basic ideas and recent developments.