This is a three term course providing an introduction to the basic concepts and results of the mathematical theory of computation and computational complexity theory. It requires no essential prerequisites, except perhaps some familiarity with somewhat abstract mathematical reasoning, at the level of a course like Math 5.

The Fall term will be first devoted to the discussion of various theoretical models of computation, like Turing machines, register machines, Markov algorithms, and recursive functions. We will demonstrate their equivalence and discuss Church's Thesis. Then we will study the basic theory of computable functions and effectively enumerable sets on the integers. We will use this theory to show that certain problems, like the so-called Halting Problem for Turing machines, are undecidable, i.e., cannot be solved algorithmically.

In the Winter term, we will first discuss the connections of the theory of undecidabilty to mathematical logic and number theory. Some of the highlights here are a detailed development of the Gödel Incompleteness Theorems and the solution of the Hilbert Tenth Problem (the nonexistence of algorithms for deciding the solvability of diophantine equations over the integers). Finally, we will discuss many other examples of undecidable problems from logic, number theory, group theory, combinatorics, and computer science. No prior knowledge of any of these subjects is assumed. We will develop all the necessary background.

In the Spring term, we will start with a discussion of decidable problems, i.e., problems for which there are actually algorithms for their solution. Then we will introduce the basic concepts of the theory of computational complexity of algorithms. We will consider decidable problems of exponential and superexponential complexity. Finally we will study the concept of feasible (polynomial time) computation and the relationship between deterministic polynomial (P) and nondeterministic polynomial (NP) computations, including NP-complete problems and the famous "P = NP" problem.

Grade:  The grade for this course will be based on the homework assignments.

Homework Policy:  In each homework there will be one starred problem on which no collaboration is allowed. For the other problems, collaboration is allowed but you should write up your own solutions. You cannot look up solutions to the problems from any source, including books, earlier years' solutions, etc. No late submissions are allowed except for medical problems (note needed from the health center) or serious personal difficulties (note needed from the Dean's Office).

There will be no textbook for this course.