CPSC 506-101 Page, Fall 2008
This page concerns CPSC 506 Section 101, for Winter 2008-09 term I
(i.e., Fall 2008).
This page has the most up-to-date information on the course and
supersedes any other document.
The focus of this course is the P vs. NP problem.
More broadly we will study aspects of complexity theory,
interplay between various computational resources
required of algorithms; these resources include space, time, randonmess,
This interplay is often stated in terms of complexity classes, such as
DTIME(f(n)), NTIME(f(n)), DSPACE(f(n)),
NSPACE(f(n)), RTIME(f(n)), etc., for a variable function, f,
and in particular
P, NP, NC, PSPACE, RP, BPP, #P, etc., and the relationships
We shall primarily follow
notes from Steven Rudich's complexity theory
class taught in 2000, although we will spend more time on certain topics
and skip or briefly mention others.
Professor Rudich's course
website contains additional material.
Another excellent source for basic complexity theory is
For the second part of the course we will also use two more terrific
material on lower bounds by
Jukna meant to supplement his book on Extremal Combinatorics, and a
of a book on complexity theory by
Sanjeev Arora and
see also Arora's
Spring 2001, lecture 22 notes on Natural Proofs.
CS506 from Spring 2007
The Fall 2008 CPSC 506 will be very similar
(but not identical) to the CPSC 506 course I gave in 2006-07.
Here are those materials; they include notes
which I'll refer to and use (although there may be omissions, new material,
and possibly some reworked material).
Here are some of my notes for class for this
year; they are in random order, and in plain text (and therefore look
horrid); use at your own risk: not all this stuff will be covered in
class, and some may change.
Homework problems will be assigned during class and collected periodically.
Homework 2, which is a work in progress at present.
I will hold office hours
by appointment (for as long as
this is feasible); just e-mail me and tell me when you are
free to meet. During hectic times I may revert to limited office hours
at fixed times.
The main new topic this year is formula size complexity (which will replace
a discussion of Razborov-Rudich). We will study Hastad's article:
The Shrinkage Exponent of DeMorgan Formulas is 2, SIAM Journal on Computing,
1998, Vol 27, pp48-64. This gives explicit functions in NP with formula
size roughly at least n^3, which is the best such result to date.
This article is available, for example, from Hastad's homepage (see the
copyright notice) or from
SIAM Journal on Computing; as fas as I know, it can be read entirely
from what we know (e.g., we know that there exist functions on k Boolean
variables of minimum formula size roughly 2^k/log(k) ).|