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.