Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Loosely speaking, the computability approach to problem solving goes like this: a set is given, and we seek an algorithm which tells us whether an object is in the set. For instance, the set might be the collection of unknotted simple closed curves in R3 with integer coordinates. Given a simple closed curve in R3 with integer coordinates, our algorithm should decide whether that curve is unknotted (and hence a member of the set). If such an algorithm exists, we call the problem Decidable; otherwise we call the problem Undecidable. Turing machines (and therefore modern computers) are fundamentally inadequate for handling undecidable problems, whereas decidable problems are *technically* doable.

That's all very nice, but even decidable problems can be computationally infeasible in any practical amount of time. This is where computational complexity enters the picture. It's no longer enough that some algorithm can decide the problem; we want one which decides the problem *efficiently*. We'll see a few notions of efficiency, emphasizing time over space. I hope to explain the distinction between P, NP, and NP-Complete problems, and give examples of each.