The main research goals of this project are to study new analytical techniques for elucidating the internal structure of complexity classes. These techniques adapt the theories of Lebesgue measure and Baire category to computational complexity. They provide quantitative methods to differentiate `typical` from `exceptional` properties of languages in a particular class, shedding light on the relationships between the structure and intrinsic difficulty of computational problems. These concepts are also closely related to the study of pseudorandom and `pseudo-generic` sequences. Improvements to some of these analytic techniques are explored, and new types of complexity-theoretic Baire category and their applications are investigated. The Educational Component of this CAREER Grant includes the goals of: (a) Establishing theoretical computer science as an integral part of the undergraduate curriculum at the University of Southern Maine, expanding the theory offerings and more closely tying theory with applications and with other subjects; (b) Implementing innovative ways to attract nonmajors to the computer science department, especially those who are interested in computer science, but may not be ready for a traditional first programming course. The routes to these goals run through teaching, advising, mentoring, and curriculum development. (This educational component is part of the Research at Undergraduate Institutions Program.)

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Communication Foundations (CCF)
Application #
9501794
Program Officer
Yechezkel Zalcstein
Project Start
Project End
Budget Start
1995-07-01
Budget End
1999-06-22
Support Year
Fiscal Year
1995
Total Cost
$91,184
Indirect Cost
Name
University of Southern Maine
Department
Type
DUNS #
City
Portland
State
ME
Country
United States
Zip Code
04104