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.

Calendar (ICS file) download, for import into your favourite calendar application

UNCLUTTER for printing

AUTHENTICATE to mark the scnews item as read