Campus Event Calendar
Event Entry
What and Who
Geometric Complexity Theory: An ambitious approach towards P versus NP
Christian Ikenmeyer
MMCI
Joint Lecture Series
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI
Public Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 6 September 2017
12:15
60 Minutes
E1 5
002
Saarbrücken
Abstract
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.
Contact
Jennifer Müller
2900
--email hidden
passcode not visible
logged in users only
Jennifer Müller, 08/24/2017 12:24 -- Created document.