Type: Seminar

Distribution: World

Expiry: 16 Aug 2012

Auth: gilesg@bari.maths.usyd.edu.au

Hindsight has a tendency to devalue mathematical effort. How difficult could it possibly be to latch onto a key insight, if we can easily observe its obvious correctness once we’ve become aware of it? The P vs NP problem provides a sophisticated formulation of this question from the perspective of theoretical computer science. Notoriously unresolved, the problem has built up a substantial lore over the past 40 years - "Is P = NP?" is often considered one of the deepest questions ever asked. The aim of this talk will be to provide an accessible introduction to the P vs NP problem, with an emphasis on the relevance of the problem to the philosophy of mathematics. Along the way, the theory of NP-completeness will also be developed, which provides a powerful framework for evidencing the difficulty of a large class of problems which pervade the modern world.