Universiteit Leiden

nl en

Lezing | Studium Generale

What Makes Network Problems Hard to Solve? Transitions in Computational Complexity

Datum
27 maart 2017
Tijd
Toelichting
Free entrance. Open to all. No prior registration required.
Serie
Complex Networks: Challenges and Perspectives
Bezoekadres
Lipsius
Cleveringaplaats 1
2311 BD Leiden
Zaal
011

This lecture is about practically relevant problems on networks and their difficulty, ranging from simple problems to problems that seem to be almost impossible to solve – even on parallel computers. Many of the very difficult problems are related to complex networks: for instance finding optimal round trips, detecting community structures, or finding energy minimal states in crystal structures. Surprisingly, often problems that are at first glance very similar to these problems, such as finding a shortest path or finding energy minimal states on planar lattices, can be solved in short time. Complex network theory has recently offered a partial understanding of what, essentially, makes problems difficult to solve. This research might shed a new light to one of the biggest unsolved problems in computer science and mathematics – the 'NP not equals P' conjecture. 

Speaker: Dr Michael Emmerich, Associate professor; Algorithms and Software Technology, Leiden Institute of Advanced Computer Science, Leiden University

Lees meer