pcmi.jpg (2782 bytes)  

Clay Mathematics Institute/Park City Mathematics Institute Undergraduate Program, Summer 2000

Organizer: Robert Bryant, Duke University



The Clay Mathematics Institute/Park City Mathematics Institute (CMI-PCMI) Undergraduate Program provides opportunities for talented undergraduate students to enhance their interest in mathematics. This program is open to undergraduates at all levels, from first-year students to those who have just completed their undergraduate education. Based on the backgrounds of the accepted students, they will be divided into two groups - introductory and advanced. There will be several activities organized for these groups, with some specifically intended for either the introductory or advanced group. There will be time for study groups and individual projects guided by advisors, as well as other activities.

Lecturers:
David M. Barrington, University of Massachusetts at Amherst
Alexis Maciel, Clarkson University

Course Information:

Computational complexity is the mathematical study of the resources needed to solve computational problems. We make abstract models of computation, simple enough to be analyzed mathematically but general enough to be relevant to real computation. We define resource measures such as running time, memory, and (for parallel computation) parallel time and number of processors. The basic object of the theory is a complexity class: the set of problems that can be solved in a particular model under particular resource constraints. The most interesting complexity classes are robust, meaning that they can be defined by a number of different constraints in different models.

We begin with two basic models: the Turing machine, which models general-purpose sequential computation, and the boolean circuit family, which models parallel computation. The resource measures of time and space for Turing machines and of size and depth for circuits give rise to a landscape of interrelated complexity classes. In exploring this landscape we will repeatedly encounter some particular phenomena:

  • As we introduce new computational models like branching programs, or new definitions of computation like nondeterminism or alternation, the same robust complexity classes occur.
  • Most robust classes have complete problems, that is, particular problems whose solution yields a similar solution for all problems in the class.
  • While we can exhibit many interesting upper bounds on complexity by presenting algorithms that meet constraints, there are only a few proven lower bounds. Thus it is consistent with our current knowledge that a wide spectrum of our complexity classes might "collapse" and actually be equal.

The division into basic and advanced sections will depend on the background and interests of the students. One possibility is for the advanced section to view the landscape of complexity classes through the lens of Immerman's "descriptive complexity theory". Here problems are divided into classes based on whether they can be expressed in various formal systems such as first-order logic.

Useful references are Sipser, "Introduction to the Theory of Computation" (basic section), Immerman, "Descriptive Complexity Theory" (advanced section), and Papadimitriou, "Computational Complexity" (both sections).

Further details may be obtained by contacting Robert Bryant, Undergraduate Program organizer.


Return to IAS/PCMI Summer Session 2000

Return to IAS/PCMI Home Page

Questions or concerns should be addressed to: pcmi@math.ias.edu

This page is archival material of the IAS/Park City Mathematics Institute