Overview Schedule Assignments Resources

this kind of complexity

but not this kind of complexity

Math 441: Intro to Computability and Complexity

Computability theory is the classical study of what problems are solvable mechanically or formulaically, say, on a computer. It's modern study was initiated by Alan Turing in 1936, with his devising of the Turing machine and his exploration of the halting problem, the first problem shown to be undecidable by a computer algorithm. This course explores these notions, building from our study of automata and languages from Math 121, and of combinatorial algorithms in Math 382.

We also begin survey of computational complexity theory--- the classification of problems based on the computational resources they require for their solution. In the case of Turing machines, we explore what's solvable when we impose limits on the time and space used by a computation. We'll start with the theory of P (problems typically feasibly solved) versus NP (problems whose solutions can be easily checked), and NP-completeness (problems that seem to require exhaustive search), and look at the wealth of seemingly disparate problems for which we still can't find reasonable algorithms and how they are related to each other. We'll also look at more general theorems that give rise to a hierarchy of problem families and those theorems that suggest limits to our ability to truly distinguish these families.

In the nearly 40 years since "P=NP?" was first formulated, tons of interesting computational models have been conceived beyond Turing's machines, and so too has sprung a wealth of problem classifications (see Aaronson's zoo). Time in the course permitting, we'll also survey some of these--- say, circuits for exploring the limits of parallel computation; computations that employ coin flips as a (possibly?) useful resource; communication- and resource-limited schemes by which a party can convince another that a solution exists. These all have proved to be robust models in that they provide alternative characterization of the families defined by simpler Turing machine models.

Depending on interest (or, alternatively), I'd like us to play with how computational complexity arises in the study of puzzles and games. [see also Bob Hearn's and Brandon's papers for some nice demonstrations]

Meeting times

Lecture: 9:00am-9:50am Mon, Wed, Fri in Library 387

Personnel

Instructor: Jim Fix, Library 314

Office hours: Soon to be posted, but feel free to come by my office or make an appointment.

We will be using Sipser's Introduction to the Theory of Computation. Part II of the text introduces Turing machines and computability. Part III surveys topics in complexity theory.

Arora and Borak have a draft of a book on computational complexity. Part I of the text ought to serve as a nice supplement to Sipser's materials, and the remainder of the book covers more advanced topics.

There are other traditional texts that you might find useful. I'll put mine and the libraries' copies on the math lab's shelves (Library 382) for your reference. I'll also post links to relevant sites and (sometimes irreverent) blogs on computation theory here.

For now, I'll keep this tentative. This is roughly the breakdown from my 2002 version of the course.
Week 1-2: Turing machines, decidability, diagonalization
Week 3-5: time-bounded Turing machines, P, NP, reductions, completeness
Week 6-7: space-bounded Turing machines, L, NL, PSPACE
Week 9: hierarchy theorems, Ladner's theorem
Week 10+:

There will be written homework assigned regularly throughout the semester, roughly, one exercise every two weeks. Since the class size is small, I encourage you to work together on the problems and with me, but write up your solutions independently.