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.)
