Spring 2005: Limits of Computation

# Spring 2005: Limits of Computation

22c:131, Sec 001

Time and Place: 9.30--10.45, TTh, 118 MLH

Here is the updated first day handout which includes TA and office hour information.

What we covered each week
The midterm is during class hours on March 10.

Homework 1 , due Feb 17.

Homework 2 , due Mar 3.

Homework 3 , due April 5.

Homework 4 , due April 21.

Homework 5 , due May 3.

The endterm is from 7.30--9.30 am on Friday, May 13, in 118 MLH

Solution sketches for some homework problems

This course is being offered for the first time, and I am quite excited about it. A brief description follows.

-- We will begin by introducing the notion of a Turing machine, a concept of great historical importance in formalizing the notion of computation and the development of the modern digital computer. We will argue that it indeed does capture the notion of a computer program/ computer. The notion of a Turing machine is important to us today because it is a model that lets us study in a formal way what algorithmic problems are solvable, and what problems are effectively solvable.

-- Having used the Turing machine to define what it means for an algorithmic problem to be solvable by a computer program, we will begin the study of unsolvable problems. We will show that the halting problem is unsolvable -- this tells us that there is no computer program that predicts the behaviour of a given computer program, or certifies that a given program does what it was designed to do. Using the notion of reducibility, we will then show that many other natural problems are unsolvable.

-- We then use the Turing machine to study effective computability, that is, what problems are solvable if resources such as space/time are in limited supply. We focus on polynomial running time, introduce a class of problems called NP, which contains many problems that arise frequently in practice. We raise arguably the central question in theoretical computer science, which is whether all problems in NP are solvable by programs with polynomial running time. (That is, is NP contained in the class P of problems solvable by programs with polynomial running time?) We introduce the notion of NP-complete problems; these are problems in NP that are provably as hard as every other problem in NP. We then prove the famous result that the boolean satisfiability problem is NP-complete. This is then used to establish the NP-completeness of several other problems like the clique and the travelling salesman problem.

-- We introduce the notion of probabilistic algorithms, which are programs that have access to random bits. We define classes of problems that are solvable in polynomial time by probabilistic algorithms. We study the relationship between these classes and the connection with the classes NP and P. This brings us to another central question, which is whether random bits really give additional power as far as polynomial time solvability is concerned.

-- We introduce complexity classes appropriate for approximation algorithms that run in polynomial time, and study the equivalent of NP-completeness here.

-- We consider some other topics: Interactive proofs and their power, space bounded computation, and the connection IP = PSPACE; Cryptography, which is one nice consequence of the existence of certain kind of intractable problems; and Communication Complexity.

Evaluation will be based on 5--6 homeworks (involving concepts and proofs) and two exams.