SMS scnews item created by Giles Gardam at Thu 9 Aug 2012 1116
Type: Seminar
Distribution: World
Expiry: 16 Aug 2012
Calendar1: 9 Aug 2012 1300-1400
CalLoc1: Carslaw 373
Auth: gilesg@bari.maths.usyd.edu.au

SUMS: McLellan -- P vs NP: The Problem of Insight

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.