|
||
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.
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:
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 Questions or concerns should be addressed to: pcmi@math.ias.edu This page is archival material of the IAS/Park City Mathematics Institute |