Lezing | Studium Generale
What Makes Network Problems Hard to Solve? Transitions in Computational Complexity
- 27 maart 2017
- Free entrance. Open to all. No prior registration required.
- Complex Networks: Challenges and Perspectives
2311 BD Leiden
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